/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BDR30/FONT#2=BAXM30/FONT#3=BASB30/FONT#4=BDR30/FONT#5=SUB/FONT#6=SUP/FONT#9=FIX40/FONT#10=FIX30/FONT#11=GRFX25/FONT#12=GRFX35
␈↓ ↓H␈↓␈↓ εP␈↓ Oi


␈↓ ↓H␈↓␈↓ ∧P␈↓&T A B L E   O F   C O N T E N T S␈↓)αβ




␈↓ ↓H␈↓SECTION␈↓ PAGE




␈↓ ↓H␈↓I␈↓ α8INTRODUCTION TO LISP

␈↓ ↓H␈↓␈↓ βλ1␈↓ ∧(Lists.␈↓ ¬_.   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   ␈↓ 	h␈↓ ? 1

␈↓ ↓H␈↓␈↓ βλ2␈↓ ∧(Atoms.␈↓ ¬_.   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   ␈↓ 	h␈↓ ? 3

␈↓ ↓H␈↓␈↓ βλ3␈↓ ∧(List structures.␈↓ ¬x.   .   .   .   .   .   .   .   .   .   .   .   .   ␈↓ 	h␈↓ ? 3

␈↓ ↓H␈↓␈↓ βλ4␈↓ ∧(S-expressions.␈↓ ¬x.   .   .   .   .   .   .   .   .   .   .   .   .   ␈↓ 	h␈↓ ? 4

␈↓ ↓H␈↓␈↓ βλ5␈↓ ∧(The basic functions and predicates of LISP.␈↓ λx.   .   .   ␈↓ 	h␈↓ ? 6

␈↓ ↓H␈↓␈↓ βλ6␈↓ ∧(Conditional expressions.␈↓ εX.   .   .   .   .   .   .   .   .   .   .   ␈↓ 	h␈↓ ? 9

␈↓ ↓H␈↓␈↓ βλ7␈↓ ∧(Boolean expressions.␈↓ ε(.   .   .   .   .   .   .   .   .   .   .   .   ␈↓ 	h␈↓ 0 11

␈↓ ↓H␈↓␈↓ βλ8␈↓ ∧(Recursive function definitions.␈↓ π8.   .   .   .   .   .   .   .   ␈↓ 	h␈↓ 0 12

␈↓ ↓H␈↓␈↓ βλ9␈↓ ∧(Lambda expressions and functions with functions as
␈↓ ↓H␈↓␈↓ ¬(arguments.␈↓ ε(.   .   .   .   .   .   .   .   .   .   .   .   ␈↓ 	h␈↓ 0 18

␈↓ ↓H␈↓␈↓ βλ10␈↓ ∧(Label.␈↓ ¬_.   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   ␈↓ 	h␈↓ 0 20


␈↓ ↓H␈↓II␈↓ α8HOW TO WRITE RECURSIVE FUNCTION DEFINITIONS

␈↓ ↓H␈↓␈↓ βλ1␈↓ ∧(Static and dynamic ways of programming.␈↓ λH.   .   .   .   ␈↓ 	h␈↓ 0 22

␈↓ ↓H␈↓␈↓ βλ2␈↓ ∧(Simple list recursion.␈↓ ε(.   .   .   .   .   .   .   .   .   .   .   .   ␈↓ 	h␈↓ 0 23

␈↓ ↓H␈↓␈↓ βλ3␈↓ ∧(Simple S-expression recursion.␈↓ π8.   .   .   .   .   .   .   .   ␈↓ 	h␈↓ 0 25

␈↓ ↓H␈↓␈↓ βλ4␈↓ ∧(Other structural recursions.␈↓ πλ.   .   .   .   .   .   .   .   .   ␈↓ 	h␈↓ 0 26

␈↓ ↓H␈↓␈↓ βλ5␈↓ ∧(Tree search.␈↓ ¬H.   .   .   .   .   .   .   .   .   .   .   .   .   .   .   ␈↓ 	h␈↓ 0 27

␈↓ ↓H␈↓␈↓ βλ6␈↓ ∧(Game trees.␈↓ ¬H.   .   .   .   .   .   .   .   .   .   .   .   .   .   .   ␈↓ 	h␈↓ 0 30
␈↓ ↓H␈↓␈↓ εP␈↓ I1


␈↓ ↓H␈↓β␈↓ ¬yCHAPTER I

␈↓ ↓H␈↓β␈↓ ¬∞INTRODUCTION TO LISP






␈↓ ↓H␈↓1.  ␈↓βLists.␈↓


␈↓ ↓H␈↓        Symbolic␈α
information␈α
in␈α
LISP␈α
is␈α expressed␈α
 by␈α
 S-expressions␈α
and␈α
 these␈α
 are␈α represented
␈↓ ↓H␈↓in␈α∂ the␈α∂ memory␈α∞of␈α∂the␈α∂computer␈α∂by␈α∞list␈α∂structures.␈α∂Before␈α∞giving␈α∂formal␈α∂ definitions,␈α∂ we␈α∞ shall
␈↓ ↓H␈↓give  some examples.

␈↓ ↓H␈↓        The most common form of S-expression is the  list,  and  here are some lists:

␈↓ ↓H␈↓The list
␈↓ ↓H␈↓        ␈↓∧(A B C E)
␈↓ ↓H␈↓∧␈↓has four elements.

␈↓ ↓H␈↓The list
␈↓ ↓H␈↓        ␈↓∧(A B (C D) E)
␈↓ ↓H␈↓∧␈↓has four elements one of which is itself a list.

␈↓ ↓H␈↓The list
␈↓ ↓H␈↓        ␈↓∧(A)
␈↓ ↓H␈↓∧␈↓has one element.

␈↓ ↓H␈↓The list
␈↓ ↓H␈↓        ␈↓∧((A B C D))
␈↓ ↓H␈↓∧␈↓also has one element which itself is a list.

␈↓ ↓H␈↓The list
␈↓ ↓H␈↓        ␈↓∧()
␈↓ ↓H␈↓∧␈↓has no elements; it is also written
␈↓ ↓H␈↓        ␈↓∧NIL.
␈↓ ↓H␈↓∧␈↓The list
␈↓ ↓H␈↓        ␈↓∧(PLUS X Y)
␈↓ ↓H␈↓∧␈↓has three elements and may be used to represent the expression
␈↓ ↓H␈↓        ␈↓αx␈↓↓ + ␈↓αy.

␈↓ ↓H␈↓α␈↓The list
␈↓ ↓H␈↓        ␈↓∧(PLUS (TIMES X Y) X 3)
␈↓ ↓H␈↓∧␈↓has four elements and may be used to represent the expression
␈↓ ↓H␈↓        ␈↓αxy␈↓↓ + ␈↓αx␈↓↓ + ␈↓∧3.
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ I2


␈↓ ↓H␈↓∧␈↓The list
␈↓ ↓H␈↓        ␈↓∧(EXIST X (ALL Y (IMPLIES (P X) (P Y))))
␈↓ ↓H␈↓∧␈↓may be used to represent the logical expression
␈↓ ↓H␈↓        ␈↓↓(∃␈↓αx␈↓↓)(∀␈↓αy␈↓↓).␈↓αP␈↓↓(␈↓αx␈↓↓)⊃␈↓αP␈↓↓(␈↓αy␈↓↓).

␈↓ ↓H␈↓↓␈↓The list
␈↓ ↓H␈↓        ␈↓∧(INTEGRAL 0 ∞ (TIMES (EXP (TIMES I X Y)) (F X)) X)
␈↓ ↓H␈↓∧␈↓may be used to represent the expression

␈↓ ↓H␈↓        ␈↓␈↓#v0␈↓#␈↓	␈␈↓␈↓#
∞␈↓#␈↓αe␈↓εixy␈↓αf␈↓↓(␈↓αx␈↓↓)␈↓αdx.

␈↓ ↓H␈↓α␈↓The list
␈↓ ↓H␈↓        ␈↓∧((A B) (B A C D) (C B D E) (D B C E) (E C D F) (F E))

␈↓ ↓H␈↓is␈α
used␈αto␈α
represent␈α
the␈αnetwork␈α
of␈α
Figure␈α1␈α
according␈α
 to␈α a␈α
 scheme␈α
whereby␈α there␈α
 is␈α
a␈αsublist
␈↓ ↓H␈↓for each vertex consisting of the vertex itself followed by the vertices to which it is connected.

␈↓"␈↓ ↓H␈↓␈↓ βX                    C
␈↓"∧␈↓ ↓H␈↓␈↓ βX                  ≤'~`≥
␈↓"␈↓ ↓H␈↓␈↓ βX                ≤'  ~  `≥
␈↓"␈↓ ↓H␈↓␈↓ βX            B ≤'    ~    `≥ E
␈↓"␈↓ ↓H␈↓␈↓ βX  A ααααααααα'      ~      `ααααααααα F␈↓ ↓H                              ≥             ≤
␈↓"␈↓ ↓H␈↓␈↓ βX              `≥    ~    ≤'
␈↓"␈↓ ↓H␈↓␈↓ βX                `≥  ~  ≤'
␈↓"␈↓ ↓H␈↓␈↓ βX                  `≥~≤'
␈↓"
␈↓ ↓H␈↓␈↓ βX                    D

␈↓"␈↓ ↓H␈↓␈↓ βX                             Figure 1

␈↓ ↓H␈↓        The␈α∞ elements␈α∞ of␈α∂ a␈α∞ list␈α∞ are␈α∂surrounded␈α∞by␈α∞parentheses␈α∞and␈α∂separated␈α∞by␈α∞spaces.␈α∂ A␈α∞list
␈↓ ↓H␈↓may␈αhave␈αany␈αnumber␈αof␈αterms␈αand␈αany␈α of␈αthese␈α terms␈α may␈α themselves␈α be␈α lists.␈α  In␈α this␈αcase,
␈↓ ↓H␈↓the␈αspaces␈αsurrounding␈αa␈α
sublist␈α may␈α be␈α omitted,␈α and␈α
 extra␈α spaces␈α between␈αelements␈αof␈α
a␈αlist
␈↓ ↓H␈↓are allowed.  Thus the lists

␈↓ ↓H␈↓        ␈↓∧(A B(C  D)    E)

␈↓ ↓H␈↓∧␈↓and

␈↓ ↓H␈↓        ␈↓∧(A B (C D) E)

␈↓ ↓H␈↓∧␈↓are regarded as the same.
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ I3


␈↓ ↓H␈↓2.  ␈↓βAtoms.␈↓


␈↓ ↓H␈↓        The␈αexpressions␈α␈↓∧A,␈αB,␈αX,␈αY,␈α3,␈αPLUS,␈α␈↓and␈α␈↓∧ALL␈↓␈αoccurring␈αin␈αthe␈αabove␈α lists␈αare␈αcalled␈αatoms.
␈↓ ↓H␈↓In␈α
general,␈α∞an␈α
atom␈α
is␈α∞expressed␈α
by␈α
a␈α∞sequence␈α
of␈α
capital␈α∞letters,␈α
 digits,␈α
 and␈α∞ special␈α
 characters
␈↓ ↓H␈↓with␈α∩certain␈α∩ exclusions.␈α∩  The␈α∩exclusions␈α∩are␈α∩<space>,␈α∩<carriage␈α∩return>,␈α∩and␈α∩the␈α∩other␈α∩non-
␈↓ ↓H␈↓printing␈α∂ characters,␈α∞ and␈α∂ also␈α∞ the␈α∂ parentheses,␈α∞brackets,␈α∂ semi-colon,␈α∞ and␈α∂ comma.␈α∞  Numbers
␈↓ ↓H␈↓are␈α⊂expressed␈α⊂as␈α⊂signed␈α⊂decimal␈α⊂or␈α⊂octal␈α⊂numbers,␈α⊂ the␈α⊂ exact␈α⊂ convention␈α⊂ depending␈α⊃ on␈α⊂ the
␈↓ ↓H␈↓implementation.␈α~ Floating␈α~ point␈α~ numbers␈α~ are␈α~ written␈α~ with␈α~decimal␈α~points␈α~and,␈α~when
␈↓ ↓H␈↓appropriate,␈α∪an␈α∪exponent␈α∪notation␈α∪depending␈α∪ on␈α∪ the␈α∪implementation.␈α∪  The␈α∪ reader␈α∩ should
␈↓ ↓H␈↓consult the programmer's manual for the LISP implementation he intends to use.

␈↓ ↓H␈↓        Some examples of atoms are

␈↓ ↓H␈↓        ␈↓∧THE-LAST-TRUMP
␈↓ ↓H␈↓∧␈↓        ␈↓∧A307B
␈↓ ↓H␈↓∧␈↓        ␈↓∧345
␈↓ ↓H␈↓∧␈↓        ␈↓∧3.14159,

␈↓ ↓H␈↓∧␈↓and from these we can form lists like

␈↓ ↓H␈↓        ((345 3.14159 -47) A307B THE-LAST-TRUMP -45.21).  



␈↓ ↓H␈↓3.  ␈↓βList structures.␈↓


␈↓ ↓H␈↓        Lists␈α
 are␈α
 represented␈α
in␈α
the␈α
memory␈α
of␈α
the␈α
computer␈α
by␈α
list␈α
structures.␈α
   A␈α
list␈α
structure␈αis␈α
a
␈↓ ↓H␈↓collection␈αof␈αmemory␈αwords␈α each␈αof␈α which␈α is␈α divided␈α into␈α two␈α parts,␈αand␈αeach␈αpart␈αis␈αcapable
␈↓ ↓H␈↓of␈αcontaining␈αan␈αaddress␈αin␈αmemory.␈αThe␈αtwo␈αparts␈αare␈αcalled␈αare␈α called␈αthe␈α a-part␈α and␈α the␈α d-
␈↓ ↓H␈↓part.␈α⊂ There␈α⊂ is␈α⊂ one␈α⊂computer␈α⊃word␈α⊂for␈α⊂each␈α⊂element␈α⊂of␈α⊂the␈α⊃list,␈α⊂and␈α⊂the␈α⊂a-part␈α⊂of␈α⊃the␈α⊂word
␈↓ ↓H␈↓contains␈α⊂the␈α∂ address␈α⊂of␈α∂the␈α⊂list␈α∂or␈α⊂atom␈α∂representing␈α⊂the␈α∂element,␈α⊂and␈α∂the␈α⊂d-part␈α⊂contains␈α∂the
␈↓ ↓H␈↓address␈α
of␈α
the␈α
word␈α
representing␈α
the␈α
next␈α
element␈α
 of␈α
 the␈α
 list.␈α
 If␈α
the␈α
list␈α
element␈α
is␈α
itself␈α
a␈α
list,
␈↓ ↓H␈↓then,␈α∞of␈α∞course,␈α∞the␈α∞address␈α∞of␈α
the␈α∞first␈α∞word␈α∞of␈α∞its␈α∞list␈α
structure␈α∞is␈α∞given␈α∞in␈α∞the␈α∞ a-part␈α∞ of␈α
 the
␈↓ ↓H␈↓word␈α∂ representing␈α∂ that␈α∂ element.␈α∂ A␈α∂diagram␈α⊂shows␈α∂this␈α∂more␈α∂clearly␈α∂than␈α∂words,␈α∂and␈α⊂the␈α∂list
␈↓ ↓H␈↓structure␈α∩corresponding␈α∩to␈α∩the␈α∩ list␈α∩  ␈↓∧(PLUS␈α∩(TIMES␈α⊃ X␈α∩ Y)␈α∩ X␈α∩ 3)␈↓␈α∩  which␈α∩may␈α∩represent␈α⊃the
␈↓ ↓H␈↓expression  ␈↓αxy␈↓↓ + ␈↓αx␈↓↓ + ␈↓∧3  is shown in figure 2.
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ I4




␈↓"␈↓ ↓H␈↓        ⊂αααπααα⊃     ⊂αααπααα⊃     ⊂αααπααα⊃     ⊂αααπααα⊃
␈↓"␈↓ ↓H␈↓  ααααα→~   ~   εαααα→~   ~   εαααα→~   ~   εαααα→~   ~   εααααααα⊃
␈↓"␈↓ ↓H␈↓        %απα∀ααα$     %απα∀ααα$     %απα∀ααα$     %απα∀ααα$       ~
␈↓"␈↓ ↓H␈↓          ↓             ~             ~             ↓             ~
␈↓"␈↓ ↓H␈↓         PLUS           ~             ~             3             ~
␈↓"␈↓ ↓H␈↓                        ~  ⊂αααπααα⊃  ~  ⊂αααπααα⊃     ⊂αααπααα⊃  ~
␈↓"␈↓ ↓H␈↓                        %α→~   ~   εααβα→~   ~   εαααα→~   ~   ~  ~
␈↓"␈↓ ↓H␈↓                           %απα∀ααα$  ~  %απα∀ααα$     %απα∀απα$  ~
␈↓"␈↓ ↓H␈↓                             ↓        ~    ~             ↓   ~    ~
␈↓"␈↓ ↓H␈↓                           TIMES      %απαα$             Y   %ααπα$
␈↓"␈↓ ↓H␈↓                                        ↓                       ↓
␈↓"␈↓ ↓H␈↓                                        X                      NIL


␈↓"␈↓ ↓H␈↓                              Figure 2.

␈↓ ↓H␈↓∧␈↓        ␈↓∧Atoms␈α⊗ are␈α↔ represented␈α⊗ by␈α↔ the␈α⊗ addresses␈α⊗of␈α↔their␈α⊗property␈α↔lists␈α⊗which␈α↔are␈α⊗list
␈↓ ↓H␈↓∧structures␈αof␈αa␈αspecial␈αkind␈α depending␈α on␈α the␈αimplementation.␈α  (In␈α some␈α implementations,␈α the
␈↓ ↓H␈↓∧first␈α∪ word␈α∪ of␈α∪a␈α∪property␈α∪list␈α∪is␈α∪in␈α∪a␈α∪special␈α∪are␈α∪of␈α∪memory,␈α∪in␈α∪others␈α∪the␈α∪first␈α∀word␈α∪is
␈↓ ↓H␈↓∧distinguished␈α∂ by␈α∞ sign,␈α∂in␈α∞still␈α∂others␈α∞it␈α∂has␈α∂a␈α∞special␈α∂a-part.␈α∞ For␈α∂basic␈α∞LISP␈α∂programming,␈α∂it␈α∞is
␈↓ ↓H␈↓∧enough␈α
 to␈α
 know␈α
 that␈α∞ atoms␈α
 are␈α
distinguishable␈α
 from␈α∞ other␈α
 list␈α
 structures␈α
 by␈α∞a␈α
predicate
␈↓ ↓H␈↓∧called ␈↓βat␈↓.)

␈↓ ↓H␈↓        The␈α last␈α
 word␈α of␈α
 a␈αlist␈α
cannot␈αhave␈α
the␈αaddress␈αof␈α
a␈αnext␈α
word␈αin␈α
its␈αd-part␈α
since␈αthere
␈↓ ↓H␈↓isn't any next word,  so  it  has  the address of a special atom called  ␈↓∧NIL␈↓.

␈↓ ↓H␈↓        A␈α∪ list␈α∪ is␈α∪ referred␈α∪ to␈α∪ by␈α∪giving␈α∪the␈α∪address␈α∪of␈α∪its␈α∪first␈α∪element.␈α∪ According␈α∪to␈α∪this
␈↓ ↓H␈↓convention,␈α∂we␈α∂see␈α∂that␈α∂the␈α∂a-part␈α∂ of␈α∂ a␈α∂list␈α∂ word␈α∂ is␈α∂ the␈α∂ list␈α∂ element␈α∂ and␈α∂ the␈α∂d-part␈α∂is␈α∂a
␈↓ ↓H␈↓pointer␈αto␈αa␈αsublist␈αformed␈αby␈αdeleting␈αthe␈αfirst␈αelement.␈α Thus␈αthe␈αfirst␈αword␈αof␈αthe␈α list␈α structure
␈↓ ↓H␈↓of␈α figure␈α 2␈α contains␈α a␈α pointer␈αto␈αthe␈αlist␈αstructure␈αrepresenting␈αthe␈αatom␈α ␈↓∧PLUS␈↓,␈αwhile␈αits␈α
d-part
␈↓ ↓H␈↓points␈α∂to␈α∂the␈α∞list␈α∂ ␈↓∧((TIMES␈α∂X␈α∞Y)␈α∂X␈α∂3)␈↓.␈α∞ The␈α∂second␈α∂word␈α∞contains␈α∂the␈α∂list␈α∂structure␈α∞representing
␈↓ ↓H␈↓␈↓∧(TIMES␈α
X␈α
Y)␈↓␈α
 in␈α
 its␈α
 a-part␈α
 and␈α
 the␈α
 list␈α
 structure␈α
representing␈α
 ␈↓∧(X␈α
3)␈↓␈α
 in␈α
its␈α
d-part.␈α∞ The␈α
last
␈↓ ↓H␈↓word␈αpoints␈αto␈αthe␈α
atom␈α␈↓∧3␈↓␈α in␈αits␈α
a-part␈αand␈αhas␈αa␈α
pointer␈αto␈αthe␈αatom␈α
 ␈↓∧NIL␈↓␈α in␈αits␈α d-part.␈α This␈α
is
␈↓ ↓H␈↓consistent with the convention that  ␈↓∧NIL␈↓  represents the null list.



␈↓ ↓H␈↓4.  ␈↓βS-expressions.␈↓


␈↓ ↓H␈↓        When␈α∂we␈α∂examine␈α⊂the␈α∂way␈α∂list␈α⊂structures␈α∂ represent␈α∂ lists␈α⊂ we␈α∂see␈α∂ a␈α⊂ curious␈α∂ asymmetry.
␈↓ ↓H␈↓Namely,␈α the␈α a-part␈αof␈α
a␈αlist␈αword␈αcan␈α
contain␈αan␈αatom␈αor␈α
a␈αlist,␈αbut␈αthe␈α
d-part␈αcan␈αcontain␈αonly␈α
a
␈↓ ↓H␈↓list␈α∂ or␈α∂the␈α∞special␈α∂atom␈α∂ ␈↓∧NIL␈↓.␈α∂  This␈α∞restriction␈α∂is␈α∂quite␈α∂unnatural␈α∞from␈α∂the␈α∂computing␈α∂point␈α∞of
␈↓ ↓H␈↓view,␈α
 and␈α
 we␈α shall␈α
 allow␈α
 arbitrary␈α atoms␈α
 to␈α
inhabit␈α the␈α
 d-parts␈α
 of␈α words,␈α
but␈α
then␈αwe␈α
must
␈↓ ↓H␈↓generalize␈αthe␈αway␈αlist␈αstructures␈αare␈αexpressed␈αas␈αcharacter␈αstrings.␈αTo␈α do␈α this,␈α we␈αintroduce␈αthe
␈↓ ↓H␈↓notion of S-expression.
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ I5


␈↓ ↓H␈↓        An␈α∪ S-expression␈α∪is␈α∩either␈α∪an␈α∪atom␈α∪or␈α∩a␈α∪pair␈α∪of␈α∩S-expressions␈α∪separated␈α∪by␈α∪" . "␈α∩and
␈↓ ↓H␈↓surrounded by parentheses.   In  BNF,  we  can write

␈↓ ↓H␈↓<S-expression> ::= <atom> | (<S-expression> . <S-expression>).

␈↓ ↓H␈↓Examples of S-expressions are

␈↓ ↓H␈↓        ␈↓∧A
␈↓ ↓H␈↓∧␈↓        ␈↓∧(A . B)
␈↓ ↓H␈↓∧␈↓        ␈↓∧(A . (B . A))
␈↓ ↓H␈↓∧␈↓        ␈↓∧(PLUS (X . (Y . NIL)))
␈↓ ↓H␈↓∧␈↓        ␈↓∧(3 . 3.4)

␈↓ ↓H␈↓∧␈↓The␈α⊃spaces␈α⊃around␈α⊃the␈α⊃.␈α⊃may␈α⊃be␈α⊃ omitted␈α⊃ when␈α⊃ this␈α⊃ will␈α⊃ not␈α⊃ cause␈α⊃confusion.␈α∩  The␈α⊃only
␈↓ ↓H␈↓possible␈α∞confusion␈α
is␈α∞of␈α
the␈α∞dot␈α
separator␈α∞with␈α∞a␈α
decimal␈α∞point␈α
in␈α∞numbers.␈α
 Thus,␈α∞in␈α∞the␈α
above
␈↓ ↓H␈↓cases,␈α
we␈α
 may␈α∞ write␈α
␈↓∧(A.B),␈α
 (A.(B.A))␈↓,␈α∞ and␈α
 ␈↓∧(PLUS.(X.(Y.NIL)))␈↓,␈α
 but␈α∞if␈α
we␈α
wrote␈α∞␈↓∧(3.3.4)␈↓␈α
confusion
␈↓ ↓H␈↓would result.

␈↓ ↓H␈↓        In␈α
the␈α∞memory␈α
of␈α∞a␈α
computer,␈α∞an␈α
S-expression␈α∞ is␈α
 represented␈α∞by␈α
 the␈α∞ address␈α
of␈α∞a␈α
word
␈↓ ↓H␈↓whose␈αa-part␈α
contains␈αthe␈αfirst␈α
element␈αof␈αthe␈α
pair␈αand␈αwhose␈α
d-part␈αcontains␈αthe␈α
second␈αelement
␈↓ ↓H␈↓of␈α the␈α
 pair.␈α Thus,␈α
 the␈αS-expressions␈α ␈↓∧(A.B),␈α
 (A.(B.A))␈↓,␈αand␈α
 ␈↓∧(PLUS.(X.(Y.NIL)))␈α␈↓␈α
are␈αrepresented
␈↓ ↓H␈↓by the list structures of figure 3.


␈↓"␈↓ ↓H␈↓        ⊂αααπααα⊃                             ⊂αααπααα⊃     ⊂αααπααα⊃
␈↓"␈↓ ↓H␈↓        ~   ~   ~                             ~   ~   εαααα→~   ~   ~
␈↓"␈↓ ↓H␈↓        %απα∀απα$                             %απα∀ααα$     %απα∀απα$
␈↓"␈↓ ↓H␈↓          ↓   ↓                                 ~             ↓   ~
␈↓"␈↓ ↓H␈↓          A   B                                 ~             B   ~
␈↓"␈↓ ↓H␈↓                                                ~                 ~
␈↓"␈↓ ↓H␈↓                                                ~                 ~
␈↓"␈↓ ↓H␈↓                                                %ααααααααπαααααααα$
␈↓"␈↓ ↓H␈↓                                                         ↓
␈↓"␈↓ ↓H␈↓                                                         A

␈↓"␈↓ ↓H␈↓        ⊂αααπααα⊃     ⊂αααπααα⊃     ⊂αααπααα⊃
␈↓"␈↓ ↓H␈↓        ~   ~   εαααα→~   ~   εαααα→~   ~   ~
␈↓"␈↓ ↓H␈↓        %απα∀ααα$     %απα∀ααα$     %απα∀απα$
␈↓"␈↓ ↓H␈↓          ↓             ↓             ↓   ↓
␈↓"␈↓ ↓H␈↓         PLUS           X             Y  NIL



␈↓"␈↓ ↓H␈↓                              Figure 3.

␈↓ ↓H␈↓        Note␈αthat␈αthe␈αlist␈α␈↓∧(PLUS␈αX␈αY)␈↓␈αand␈αthe␈αS-expression␈α␈↓∧␈α(PLUS␈α.␈α(X␈α.␈α(Y␈α.␈αNIL)))␈↓␈α are␈αrepresented
␈↓ ↓H␈↓in␈α memory␈α by␈α the␈α same␈α list␈αstructure.␈α The␈αsimplest␈αway␈αto␈αtreat␈αthis␈αis␈αto␈αregard␈αS-expressions
␈↓ ↓H␈↓as␈α
primary␈α
and␈α
lists␈α
 as␈α
 abbreviations␈α for␈α
 certain␈α
 S-expressions,␈α
namely␈α
those␈α
that␈α
never␈αhave
␈↓ ↓H␈↓any␈αatom␈αbut␈α NIL␈α
 as␈αthe␈αsecond␈αpart␈αof␈α
a␈αpair.␈αIn␈αgiving␈α input␈α
 to␈α LISP,␈α either␈α the␈α list␈α
 form
␈↓ ↓H␈↓or␈α the␈α
S-expression␈α form␈αmay␈α
be␈αused␈αfor␈α
lists.␈α On␈αoutput,␈α
LISP␈αwill␈αprint␈α
a␈αlist␈αstructure␈α
as␈αa
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ I6


␈↓ ↓H␈↓list␈α as␈α far␈α as␈α it␈α can,␈α otherwise␈α as␈α an␈αS-expression.␈α Thus,␈α some␈αlist␈αstructures␈αwill␈αbe␈αprinted
␈↓ ↓H␈↓in a mixed notation, e.g. ␈↓∧((A . B) (C . D) (3))␈↓.

␈↓ ↓H␈↓        In␈αgeneral,␈αthe␈αlist␈α␈↓↓(␈↓αa␈αb␈α.␈α.␈α.␈α z␈↓↓)␈↓␈αmay␈αbe␈αregarded␈αas␈αan␈αabbreviation␈αof␈αthe␈αS-expression␈α␈↓↓(␈↓αa␈↓↓␈α.
␈↓ ↓H␈↓↓(␈↓αb␈↓↓ . (␈↓αc␈↓↓ . (... (␈↓αz . ␈↓∧NIL␈↓↓) ...)))␈↓.



␈↓ ↓H␈↓                                      Exercises

␈↓ ↓H␈↓        1. If we represent sums and products as indicated  above  and

␈↓ ↓H␈↓use␈α
 ␈↓∧(MINUS␈α
X),␈α
 (QUOTIENT␈α
X␈αY)␈↓,␈α
and␈α
 ␈↓∧(POWER␈α
X␈α
Y)␈↓␈α as␈α
representations␈α
of␈α
 ␈↓↓-␈↓αx␈↓,␈α
 ␈↓αx␈↓↓/␈↓αy␈↓,␈α
and␈α ␈↓αx␈↓εy␈↓
␈↓ ↓H␈↓respectively, then

␈↓ ↓H␈↓        a. What do the lists

␈↓ ↓H␈↓        ␈↓∧(QUOTIENT 2 (POWER (PLUS X (MINUS Y)) 3))

␈↓ ↓H␈↓∧␈↓and

␈↓ ↓H␈↓        ␈↓∧(PLUS -2 (MINUS 2) (TIMES X (POWER Y 3.3)))

␈↓ ↓H␈↓∧␈↓represent?

␈↓ ↓H␈↓        b.    How    are    the   expressions   ␈↓αxyz␈↓↓+␈↓∧3␈↓↓(␈↓αu␈↓↓+␈↓αv␈↓↓)␈↓ε-3␈↓   and ␈↓↓(␈↓αxy␈↓↓-␈↓αyx␈↓↓)/(␈↓αxy␈↓↓+␈↓αyx␈↓↓)␈↓ to be represented?

␈↓ ↓H␈↓        2. In the above  mentioned  graph  notation,  what  graph  is represented by the list

␈↓ ↓H␈↓        ␈↓∧((A D E F)(B D E F)(C D E F)(D A B C)(E A B C)(F A B C))?

␈↓ ↓H␈↓∧␈↓        ␈↓∧␈↓3.␈αWrite␈αthe␈αlist␈α␈↓∧((PLUS␈α(TIMES␈αX␈αY)␈αX␈α3)␈↓␈αas␈αan␈αS-expression.␈α This␈αis␈αsometimes␈αreferred␈αto
␈↓ ↓H␈↓as "dot-notation".

␈↓ ↓H␈↓        4.  Write  the  following  S-expressions  in list notation to whatever extent is possible:
␈↓ ↓H␈↓        a. (A . NIL)
␈↓ ↓H␈↓        b. (A . B)
␈↓ ↓H␈↓        c. ((A . NIL) . B)
␈↓ ↓H␈↓        d. ((A . B) . ((C . D) . NIL).



␈↓ ↓H␈↓5.  ␈↓βThe basic functions and predicates of LISP.␈↓


␈↓ ↓H␈↓        The␈α∂main␈α∂form␈α∞of␈α∂LISP␈α∂program␈α∂is␈α∞the␈α∂LISP␈α∂function,␈α∂and␈α∞LISP␈α∂functions␈α∂are␈α∂built␈α∞up
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ I7


␈↓ ↓H␈↓from␈αbasic␈αLISP␈αfunctions,␈αpredicates,␈αvariables␈αand␈αconstants.␈α An␈αexpression␈αwith␈αvariables␈αin␈αit
␈↓ ↓H␈↓whose␈α∀value␈α∀depends␈α∀on␈α∀the␈α∀values␈α∀of␈α∀the␈α∀variables␈α∀is␈α∀called␈α∀a␈α∀␈↓αform␈↓.␈α∀ LISP␈α∀functions␈α∪are
␈↓ ↓H␈↓constructed␈α∩from␈α⊃LISP␈α∩␈↓αforms␈↓␈α⊃which␈α∩are␈α⊃written␈α∩in␈α⊃two␈α∩languages␈α⊃-␈α∩␈↓αpublication␈α∩language␈↓␈α⊃and
␈↓ ↓H␈↓␈↓αinternal␈α∂language␈↓.␈α∂ Publication␈α∂language␈α∂is␈α∂easier␈α⊂for␈α∂people␈α∂to␈α∂read␈α∂and␈α∂write,␈α⊂but␈α∂publication
␈↓ ↓H␈↓language␈α
programs␈α
are␈α
not␈α∞S-expressions,␈α
and␈α
therefore␈α
it␈α
is␈α∞not␈α
easy␈α
to␈α
write␈α
LISP␈α∞programs␈α
to
␈↓ ↓H␈↓generate,␈α∪interpret␈α∪or␈α∪compile␈α∪other␈α∪LISP␈α∩programs␈α∪when␈α∪these␈α∪programs␈α∪are␈α∪in␈α∩publication
␈↓ ↓H␈↓language.␈α The␈αinternal␈αlanguage␈αprograms␈αare␈αS-expressions␈αand␈αare␈αharder␈αfor␈αa␈αperson␈αto␈αread
␈↓ ↓H␈↓and␈αwrite,␈αbut␈αit␈αis␈αeasier␈αfor␈αa␈αperson␈αto␈αwrite␈αa␈αprogram␈αto␈αmanipulate␈α␈↓αobject␈αprograms␈↓␈αwhen␈αthe
␈↓ ↓H␈↓object␈αprograms␈αare␈αin␈αinternal␈αlanguage.␈α Besides␈αall␈αthat,␈αmost␈αLISP␈αimplementations␈αaccept␈αonly
␈↓ ↓H␈↓internal language programs rather than some form of publication language.

␈↓ ↓H␈↓        Just␈α∂as␈α∂numerical␈α∂computer␈α∂programs␈α⊂are␈α∂ based␈α∂ on␈α∂ the␈α∂ four␈α∂arithmetic␈α⊂ operations␈α∂ of
␈↓ ↓H␈↓addition␈α⊂subtraction,␈α⊃multiplication,␈α⊂and␈α⊃division,␈α⊂and␈α⊃the␈α⊂arthmetic␈α⊃predicates␈α⊂of␈α⊃equality␈α⊂and
␈↓ ↓H␈↓comparison,␈α⊂so␈α⊂symbolic␈α⊂ computation␈α⊂ has␈α⊂ its␈α⊂basic␈α⊂predicates␈α⊂and␈α⊂functions.␈α⊂ LISP␈α⊃has␈α⊂three
␈↓ ↓H␈↓basic␈αfunctions␈αand␈αtwo␈α
predicates.␈α Each␈αwill␈αbe␈αexplained␈α
first␈αin␈αits␈αpublication␈αform,␈α
and␈αthen
␈↓ ↓H␈↓the internal form will be given.

␈↓ ↓H␈↓        First,␈α we␈αhave␈αtwo␈αfunctions␈α␈↓βa␈↓␈αand␈α␈↓βd␈↓.␈α ␈↓βa␈α␈↓αx␈↓␈αis␈αthe␈αa-part␈αof␈αthe␈αS-expression␈α␈↓∧x␈↓.␈α Thus,␈α ␈↓βa␈↓∧(A␈α.
␈↓ ↓H␈↓∧B)␈α
␈↓↓=␈α␈↓∧A␈↓,␈α
and␈α␈↓βa␈↓∧((A␈α
.␈α
B)␈α.␈α
A)␈α␈↓↓=␈α
␈↓∧(A␈α
.␈αB)␈↓.␈α
 ␈↓βd␈α␈↓αx␈↓␈α
is␈α
the␈αd-part␈α
of␈αthe␈α
S-expression␈α
␈↓αx␈↓.␈αThus␈α
␈↓βd␈↓∧(A␈α.␈α
B)␈α
␈↓↓=␈α␈↓∧B␈↓,
␈↓ ↓H␈↓and␈α␈↓βd␈↓∧((A␈α.␈αB)␈α.␈αA)␈α␈↓↓=␈α␈↓∧A␈↓.␈α
 ␈↓βa␈α␈↓αx␈↓␈αand␈α␈↓βd␈α␈↓αx␈↓␈αare␈αundefined␈αin␈α
basic␈αLISP␈αwhen␈α␈↓αx␈↓␈αis␈αan␈αatom,␈αbut␈αthey␈α
may
␈↓ ↓H␈↓have␈α
a␈α∞meaning␈α
in␈α
some␈α∞implementations.␈α
 The␈α∞internal␈α
forms␈α
of␈α∞␈↓βa␈α
␈↓αx␈↓␈α∞and␈α
␈↓βd␈α
␈↓αx␈↓␈α∞are␈α
␈↓∧(CAR␈α∞X)␈↓␈α
and
␈↓ ↓H␈↓␈↓∧(CDR␈α
X)␈↓␈α
respectively.␈α The␈α
names␈α
␈↓∧CAR␈↓␈α
and␈α␈↓∧CDR␈↓␈α
stood␈α
for␈α
"contents␈αof␈α
the␈α
address␈α
part␈αof␈α
register"
␈↓ ↓H␈↓and␈α
"contents␈αof␈α
the␈αdecrement␈α
part␈αof␈α
register"␈αin␈α
a␈α1957␈α
precursor␈αof␈α
LISP␈αprojected␈α
for␈αthe␈α
IBM
␈↓ ↓H␈↓704 computer.  The names have persisted for lack of a clearly preferable alternative.

␈↓ ↓H␈↓        A␈α⊃certain␈α∩ambiguity␈α⊃arises␈α∩when␈α⊃we␈α∩want␈α⊃to␈α∩use␈α⊃S-expression␈α∩constants␈α⊃in␈α∩the␈α⊃internal
␈↓ ↓H␈↓language.␈α
 Namely,␈αthe␈α
S-expression␈α␈↓∧A␈↓␈α
could␈αeither␈α
stand␈α
for␈αitself␈α
or␈αstand␈α
for␈αa␈α
variable␈α␈↓∧A␈↓␈α
whose
␈↓ ↓H␈↓value␈αis␈αwanted.␈α Even␈α␈↓∧(CAR␈αX)␈↓␈αis␈α
ambiguous␈αsince␈αsometime␈αthe␈αS-expression␈α␈↓∧(CAR␈αX)␈↓␈αitself␈α
must
␈↓ ↓H␈↓be␈αreferred␈αto␈αand␈αnot␈αthe␈αresult␈αof␈α
evaluating␈αit.␈α Internal␈αlanguage␈αavoids␈αthe␈αambiguity␈αby␈α
using
␈↓ ↓H␈↓␈↓∧(QUOTE␈α∀␈↓αe␈↓∧)␈↓␈α∀to␈α∃stand␈α∀for␈α∀the␈α∀S-exression␈α∃␈↓αe␈↓.␈α∀ Thus␈α∀the␈α∀publication␈α∃language␈α∀form␈α∀␈↓βa␈α∃␈↓∧(A␈α∀B)␈↓
␈↓ ↓H␈↓corresponds␈α⊂to␈α⊂the␈α⊃internal␈α⊂language␈α⊂form␈α⊃␈↓∧(CAR␈α⊂(QUOTE␈α⊂(A.B)))␈↓␈α⊂and␈α⊃both␈α⊂have␈α⊂the␈α⊃value␈α⊂␈↓∧A␈↓
␈↓ ↓H␈↓obtained by taking the ␈↓βa␈↓-part of the S-expression ␈↓∧(A.B)␈↓.

␈↓ ↓H␈↓        Since␈α
 lists␈α
 are␈α∞ a␈α
 particular␈α
 kind␈α
 of␈α∞ S-expression,␈α
the␈α
meanings␈α
of␈α∞ ␈↓βa␈↓␈α
 and␈α
 ␈↓βd␈↓␈α∞ for␈α
lists
␈↓ ↓H␈↓are also determined  by  the  above definitions.  Thus, we have

␈↓ ↓H␈↓        ␈↓βa␈↓∧(A B C D) ␈↓↓=␈↓β A

␈↓ ↓H␈↓β␈↓and

␈↓ ↓H␈↓        ␈↓βd␈↓∧(A B C D) ␈↓↓= ␈↓∧(B C D),

␈↓ ↓H␈↓∧␈↓and␈αwe␈αsee␈αthat,␈αin␈αgeneral,␈α ␈↓βa␈α␈↓αx␈↓␈α is␈αthe␈αfirst␈αelement␈αof␈α the␈α list␈α ␈↓αx␈↓,␈αand␈α ␈↓βd␈α␈↓αx␈↓␈α is␈αthe␈αrest␈αof␈αthe␈αlist,
␈↓ ↓H␈↓deleting that first element.

␈↓ ↓H␈↓        Notice␈α
 that␈α
 for␈α
S-expressions,␈α
the␈α
definitions␈α
of␈α
 ␈↓βa␈α
␈↓αx␈↓␈α
 and␈α
␈↓βd␈α
␈↓αx␈↓␈α
 are␈α
symmetrical,␈α
while␈α
for
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ I8


␈↓ ↓H␈↓lists␈α∞the␈α∞symmetry␈α∞is␈α∞lost.␈α
 This␈α∞is␈α∞because␈α∞ of␈α∞ the␈α
 unsymmetrical␈α∞nature␈α∞of␈α∞the␈α∞convention␈α
that
␈↓ ↓H␈↓defines lists in terms of S-expressions.

␈↓ ↓H␈↓        Notice,␈α
further,␈α
 our␈α
 convention␈α
 of␈α∞ writing␈α
  ␈↓βa␈↓␈α
  and␈α
  ␈↓βd␈↓  ␈α
without␈α∞ brackets␈α
 surrounding
␈↓ ↓H␈↓the␈αargument.␈α
 Also,␈αwe␈α
use␈αlower␈αcase␈α
letters␈αfor␈α
our␈αfunction␈αnames␈α
and␈αfor␈α
variables,␈αreserving
␈↓ ↓H␈↓the upper case letters for the S-expressions themselves.

␈↓ ↓H␈↓        The␈α third␈α
 function␈α ␈↓αcons␈↓↓[␈↓αx␈↓↓,␈α␈↓αy␈↓↓]␈↓␈α
 forms␈αthe␈αS-expression␈α
whose␈αa-part␈αand␈α
d-part␈αare␈α ␈↓αx␈↓␈α
 and
␈↓ ↓H␈↓␈↓αy␈↓  respectively.  Thus

␈↓ ↓H␈↓        ␈↓αcons␈↓↓[␈↓∧(A.B), A␈↓↓] = ␈↓∧((A.B).A).

␈↓ ↓H␈↓∧␈↓        ␈↓∧␈↓We␈α⊂ see␈α⊂ that␈α⊂ for␈α⊂ lists,␈α⊂  ␈↓αcons␈↓␈α⊂  is␈α⊂a␈α⊂prefixing␈α⊂operation.␈α⊂ Namely,␈α⊂ ␈↓αcons␈↓↓[␈↓αx␈↓↓,␈α⊂␈↓αy␈↓↓]␈↓␈α⊂ is␈α⊃the␈α⊂list
␈↓ ↓H␈↓obtained by putting the  element   ␈↓αx␈↓   onto the front of the list  ␈↓αy␈↓.  Thus

␈↓ ↓H␈↓        ␈↓αcons␈↓↓[␈↓∧A, (B C D E)␈↓↓] = ␈↓∧(A B C D E).

␈↓ ↓H␈↓∧␈↓If␈αwe␈αwant␈α ␈↓αcons␈↓↓[␈↓αx␈↓↓,␈α␈↓αy␈↓↓]␈↓␈α to␈α be␈α a␈α list,␈α then␈α  ␈↓αy␈↓␈α  must␈α be␈α a␈α list␈α(possibly␈αthe␈αnull␈αlist␈α ␈↓∧NIL␈↓),␈αand␈α ␈↓αx␈↓
␈↓ ↓H␈↓must␈α
be␈α
a␈αlist␈α
or␈α
an␈αatom.␈α
 In␈α
the␈αcase␈α
of␈α
S-expressions␈αin␈α
general,␈α
there␈αis␈α
no␈α
restriction␈α
on␈α the
␈↓ ↓H␈↓arguments  of   ␈↓αcons␈↓.   Usually,  we  shall  write   ␈↓αx . y␈↓   instead of ␈↓αcons␈↓↓[␈↓αx␈↓↓, ␈↓αy␈↓↓]␈↓  since this is briefer.

␈↓ ↓H␈↓        The␈α⊃internal␈α⊃language␈α⊃form␈α⊃of␈α⊃␈↓αx␈α⊃.␈α⊃y␈↓␈α⊃is␈α⊃␈↓∧(CONS␈α⊃X␈α⊃Y)␈↓.␈α⊃ The␈α⊃name␈α⊃"CONS"␈α∩comes␈α⊃from
␈↓ ↓H␈↓"construct" referring to the way ␈↓αcons[x,y]␈↓ is constructed from the free storage list.

␈↓ ↓H␈↓        The␈α first␈α
 predicate␈α is␈α
  ␈↓βat␈α␈↓αx␈↓.␈α
  ␈↓βat␈α␈↓αx␈↓␈α
  is␈α true␈α
 if␈α  the␈α
S-expression␈α ␈↓αx␈↓␈α
 is␈αatomic␈α
and␈αfalse
␈↓ ↓H␈↓otherwise.  The internal form is ␈↓∧(ATOM X)␈↓.

␈↓ ↓H␈↓        The␈α∀ second␈α∀ predicate␈α∀ is␈α∀equality␈α∀of␈α∀atomic␈α∪symbols␈α∀written␈α∀␈↓αx␈α∀␈↓βeq␈α∀␈↓αy␈↓.␈α∀Equality␈α∀of␈α∪S-
␈↓ ↓H␈↓expressions␈α∂is␈α∞tested␈α∂by␈α∞a␈α∂ program␈α∞ based␈α∂ on␈α∞␈↓βeq␈↓.␈α∂  Actually␈α∞  ␈↓βeq␈↓␈α∂ does␈α∞a␈α∂bit␈α∞more␈α∂than␈α∞testing
␈↓ ↓H␈↓equality␈αof␈α
atoms.␈α Namely,␈α ␈↓αx␈α
␈↓βeq␈α␈↓αy␈↓␈α
 is␈αtrue␈αif␈α
and␈αonly␈α
if␈αthe␈αaddresses␈α
 of␈α the␈α
 first␈αwords␈α of␈α
 the
␈↓ ↓H␈↓S-expressions␈α  ␈↓αx␈↓␈α  and␈α ␈↓αy␈↓␈α are␈αequal.␈α Therefore,␈αif␈α␈↓αx␈α␈↓βeq␈α␈↓αy␈↓,␈αthen␈α ␈↓αx␈↓␈α and␈α␈↓αy␈↓␈αare␈αcertainly␈α the␈α same
␈↓ ↓H␈↓S-expression␈α since␈αthey␈α are␈α represented␈αby␈αthe␈αsame␈αstructure␈αin␈αmemory.␈α The␈αconverse␈αis␈αfalse
␈↓ ↓H␈↓because␈αthere␈αis␈αno␈α guarantee␈α in␈α general␈α that␈α the␈α same␈αS-expression␈αis␈αnot␈αrepresented␈αby␈αtwo
␈↓ ↓H␈↓different␈αlist␈αstructures.␈α In␈αthe␈αparticular␈αcase␈αwhere␈αat␈αleast␈αone␈αof␈αthe␈αS-expressions␈αis␈α known␈αto
␈↓ ↓H␈↓be␈α
 an␈α
atom,␈α
this␈αguarantee␈α
can␈α
be␈α
given,␈α
because␈αLISP␈α
represents␈α
atoms␈α
uniquely␈α
in␈αmemory.␈α
 The
␈↓ ↓H␈↓internal form is ␈↓∧(EQ X Y)␈↓.

␈↓ ↓H␈↓        The␈αabove␈αare␈αall␈α
the␈αbasic␈αfunctions␈αof␈α
LISP;␈αall␈αother␈αLISP␈α
functions␈α can␈α be␈α built␈α
 from
␈↓ ↓H␈↓them␈α∞ using␈α∞ recursive␈α
 conditional␈α∞expressions␈α∞as␈α
will␈α∞shortly␈α∞be␈α
explained.␈α∞However,␈α∞the␈α∞use␈α
of
␈↓ ↓H␈↓certain abbreviations makes LISP programs easier to write and understand.

␈↓ ↓H␈↓        ␈↓βn␈α
␈↓αx␈↓␈α
  is␈α an␈α
 abbreviation␈α
for␈α ␈↓αx␈α
␈↓βeq␈α
␈↓∧NIL␈↓.␈α
 It␈αrates␈α
a␈α
special␈αnotation␈α
because␈α
 ␈↓∧NIL␈↓␈α
 plays␈αthe
␈↓ ↓H␈↓same␈α∞ role␈α∞ among␈α∂ lists␈α∞ that␈α∞ zero␈α∞plays␈α∂ among␈α∞ numbers,␈α∞ and␈α∞list␈α∂variables␈α∞often␈α∞have␈α∂to␈α∞be
␈↓ ↓H␈↓tested to see if their value is  ␈↓∧NIL␈↓.  Its internal form is ␈↓∧(NULL X)␈↓.

␈↓ ↓H␈↓    The␈α
notation␈α
␈↓αlist␈↓↓[␈↓αx1,␈αx2,␈α
.␈α
.␈α.␈α
,␈α
xn␈↓↓]␈↓␈αis␈α
used␈α
to␈α
denote␈αthe␈α
composition␈α
of␈α␈↓αcons␈↓'s␈α
that␈α
forms␈αa␈α
list
␈↓ ↓H␈↓from its elements.  Thus
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ I9


␈↓ ↓H␈↓        ␈↓αlist␈↓↓[␈↓αx, y, z␈↓↓] = ␈↓αcons␈↓↓[␈↓αx, cons␈↓↓[␈↓αy, cons␈↓↓[␈↓αz, ␈↓∧NIL␈↓↓]]]

␈↓ ↓H␈↓↓␈↓and␈α
forms␈α
a␈α
list␈α
of␈α
three␈α
elements␈α
out␈α
of␈α
the␈α
quantities␈α ␈↓αx,␈α
 y,␈α
␈↓␈α
 and␈α
␈↓αz␈↓.␈α
 We␈α
 often␈α
 write␈α
 ␈↓↓<␈↓αx␈α
y␈α
.␈α.␈α
.
␈↓ ↓H␈↓αz␈↓↓>␈↓␈α∩ instead␈α∩of␈α∩ ␈↓αlist␈↓↓[␈↓αx,␈α∩y,␈α∪.␈α∩.␈α∩.␈α∩,␈α∩z␈↓↓]␈↓␈α∩when␈α∪this␈α∩will␈α∩not␈α∩cause␈α∩ confusion.␈α∪ The␈α∩experienced
␈↓ ↓H␈↓implementer␈α∩of␈α∪programming␈α∩languages␈α∩will␈α∪expect␈α∩that␈α∪since␈α∩␈↓αlist␈↓␈α∩has␈α∪a␈α∩variable␈α∪number␈α∩of
␈↓ ↓H␈↓arguments,␈αits␈αimplementation␈αwill␈αpose␈αproblems.␈α He␈αwill␈αbe␈αright.␈α The␈αinternal␈αform␈αof␈α␈↓α<x␈αy␈α...
␈↓ ↓H␈↓αz>␈↓ is ␈↓∧(LIST X Y ... Z)␈↓.

␈↓ ↓H␈↓        Compositions␈αof␈α ␈↓βa␈↓␈α and␈α ␈↓βd␈↓␈α are␈αwritten␈αby␈αconcatenating␈α the␈αletters␈α  ␈↓βa␈↓␈α and␈α ␈↓βd␈↓.␈α Thus,␈αit␈αis
␈↓ ↓H␈↓easily␈α∂seen␈α∂that␈α∂ ␈↓βad␈α∂␈↓αx␈↓␈α⊂ denotes␈α∂the␈α∂second␈α∂element␈α∂of␈α∂the␈α⊂list␈α∂ ␈↓αx␈↓,␈α∂and␈α∂ ␈↓βadd␈α∂␈↓αx␈↓␈α∂ denotes␈α⊂the␈α∂third
␈↓ ↓H␈↓element of that list.

␈↓ ↓H␈↓        Besides␈αthe␈αbasic␈αfunctions␈αof␈αLISP,␈αthere␈αwill␈αbe␈αuser-defined␈αfunctions.␈α We␈αhaven't␈αgiven
␈↓ ↓H␈↓the␈α∞mechanism␈α∞function␈α∂definition␈α∞yet,␈α∞but␈α∂suppose␈α∞a␈α∞function␈α∂␈↓αsubst␈↓␈α∞taking␈α∞three␈α∂arguments␈α∞has
␈↓ ↓H␈↓been defined.  It may be used in forms like ␈↓αsubst[x,y,z]␈↓ having internal form ␈↓∧(SUBST X Y Z)␈↓.

␈↓ ↓H␈↓        As␈α∀in␈α∪other␈α∀programming␈α∪languages␈α∀and␈α∪in␈α∀mathematics␈α∪generally,␈α∀new␈α∪forms␈α∀can␈α∪be
␈↓ ↓H␈↓constructed␈αby␈αapplying␈αthe␈αfunctions␈αand␈αpredicates␈α
to␈αother␈αforms␈αand␈αnot␈αjust␈αto␈α
variables␈αand
␈↓ ↓H␈↓constants.␈α⊃ Thus␈α⊂we␈α⊃have␈α⊂forms␈α⊃like␈α⊂␈↓αsubst[x,y,␈↓βa␈α⊃z␈↓α]␈α⊂.␈α⊃subst[x,y,␈↓βd␈α⊂␈↓αz]␈↓␈α⊃involving␈α⊂a␈α⊃user␈α⊂defined
␈↓ ↓H␈↓function ␈↓αsubst␈↓.  Its internal form is ␈↓∧(CONS (SUBST X Y (CAR Z)) (SUBST X Y (CDR Z)))␈↓.



␈↓ ↓H␈↓6.  ␈↓βConditional expressions.␈↓


␈↓ ↓H␈↓        When␈αthe␈αform␈αthat␈αrepresents␈αa␈αfunction␈αdepends␈αon␈αwhether␈αa␈αcertain␈α predicate␈αis␈αtrue␈αof
␈↓ ↓H␈↓the␈α∪arguments,␈α∩conditional␈α∪expressions.␈α∩ are␈α∪used.␈α∩ The␈α∪conditional␈α∩expression␈α∪(more␈α∩properly
␈↓ ↓H␈↓␈↓αconditional form␈↓)

␈↓ ↓H␈↓        ␈↓βif ␈↓αp ␈↓βthen ␈↓αa ␈↓βelse ␈↓αb

␈↓ ↓H␈↓α␈↓is␈α∞evaluated␈α
as␈α∞follows:␈α
 First␈α∞ ␈↓αp␈↓␈α
 is␈α∞evaluated␈α∞and␈α
determined␈α∞to␈α
be␈α∞true␈α
or␈α∞false.␈α
 If␈α∞ ␈↓αp␈↓␈α∞ is␈α
true,
␈↓ ↓H␈↓then␈α ␈↓αa␈↓␈α is␈αevaluated␈αand␈α its␈α value␈αis␈α the␈α value␈α of␈α the␈α expression.␈α  If␈α  ␈↓αp␈↓␈α  is␈αfalse,␈αthen␈α ␈↓αb␈↓␈α is
␈↓ ↓H␈↓evaluated␈α∩and␈α⊃its␈α∩value␈α⊃is␈α∩the␈α⊃value␈α∩of␈α∩the␈α⊃expression.␈α∩ Note␈α⊃that␈α∩if␈α⊃␈↓αp␈↓␈α∩ is␈α⊃true,␈α∩ ␈↓αb␈↓␈α∩ is␈α⊃never
␈↓ ↓H␈↓evaluated,␈αand␈α
if␈α ␈↓αp␈↓␈α
 is␈αfalse,␈α
then␈α ␈↓αa␈↓␈α
 is␈αnever␈α
evaluated.␈α The␈α
importance␈αof␈α
this␈αwill␈αbe␈α
explained
␈↓ ↓H␈↓later.␈α∞ A␈α∞familiar␈α∞ function␈α∂that␈α∞can␈α∞be␈α∞written␈α∂conveniently␈α∞using␈α∞conditional␈α∞expressions␈α∂is␈α∞the
␈↓ ↓H␈↓absolute value of a real number.  We have

␈↓ ↓H␈↓        ␈↓↓|␈↓αx␈↓↓| = ␈↓βif ␈↓αx␈↓↓<␈↓∧0 ␈↓βthen ␈↓↓-␈↓αx ␈↓βelse ␈↓αx.

␈↓ ↓H␈↓α␈↓A more general form of conditional expression is

␈↓ ↓H␈↓        ␈↓βif ␈↓αp ␈↓βthen ␈↓αa ␈↓βelse if ␈↓αq ␈↓βthen ␈↓αb . . .  ␈↓βelse if ␈↓αs ␈↓βthen ␈↓αd ␈↓βelse ␈↓αe.

␈↓ ↓H␈↓α␈↓There␈α can␈α be␈α any␈α number␈α of␈α terms;␈α the␈α value␈α is␈αdetermined␈αby␈αevaluating␈αthe␈αpropositional
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :10


␈↓ ↓H␈↓terms␈α ␈↓αp,␈α q␈↓,␈αetc.␈αuntil␈αa␈αtrue␈αterm␈α is␈αfound;␈α the␈αvalue␈αis␈αthen␈αthat␈αof␈αthe␈αterm␈αfollowing␈αthe␈αnext
␈↓ ↓H␈↓␈↓βthen␈↓.␈α
 If␈α
none␈α
of␈α
the␈α
propositional␈α
terms␈α
is␈α
true,␈α
then␈α
the␈α
value␈α
is␈α
that␈α
of␈α
the␈α
term␈α∞following␈α
the
␈↓ ↓H␈↓␈↓βelse␈↓.

␈↓ ↓H␈↓        The function graphed in figure 4 is described by the equation

␈↓ ↓H␈↓        ␈↓αtri␈↓↓[␈↓αx␈↓↓] = ␈↓βif ␈↓αx␈↓↓<-␈↓∧1 ␈↓βthen ␈↓∧0 ␈↓βelse if ␈↓αx␈↓↓<␈↓∧0 ␈↓βthen ␈↓∧1␈↓↓+␈↓αx ␈↓βelse if ␈↓αx␈↓↓<␈↓∧1 ␈↓βthen ␈↓∧1␈↓↓-␈↓αx ␈↓βelse ␈↓∧0.


␈↓"␈↓ ↓H␈↓␈αλ                                    ~
␈↓"␈↓ ↓H␈↓␈αλ                                    ~
␈↓"␈↓ ↓H␈↓                                   ≤'`≥(0,1)␈↓ ↓H␈αλ                                    ~
␈↓"␈↓ ↓H␈↓                                 ≤'␈αλ ~␈αλ `≥
␈↓"␈↓ ↓H␈↓                               ≤'␈αλ   ~␈αλ   `≥
␈↓"␈↓ ↓H␈↓                             ≤'␈αλ     ~␈αλ     `≥
␈↓"␈↓ ↓H␈↓                            '␈αλ       ~␈αλ       `␈↓ ↓H      ======================αααααααααααααααααα======================
␈↓"␈↓ ↓H␈↓␈αλ                        (-1,0)      ~      (1,0)
␈↓"␈↓ ↓H␈↓␈αλ                                    ~
␈↓"␈↓ ↓H␈↓␈αλ                                    ~


␈↓"␈↓ ↓H␈↓                                Figure 4.

␈↓ ↓H␈↓∧␈↓        ␈↓∧The␈α
internal␈α∞form␈α
of␈α∞conditional␈α
forms␈α
is␈α∞made␈α
in␈α∞a␈α
more␈α
regular␈α∞way␈α
than␈α∞the␈α
publication
␈↓ ↓H␈↓∧form; the publication form was altered to conform to ALGOL.  We write

␈↓ ↓H␈↓∧␈↓        ␈↓∧(COND (p1 e1) (p2 e2) ... (pn en))␈↓

␈↓ ↓H␈↓with␈α
any␈α
number␈α
of␈α
terms.␈α
 Its␈α
value␈α
is␈α
determined␈α
by␈α
evaluating␈α
the␈α
␈↓∧p␈↓'s␈α
successively␈α
until␈α
one␈αis
␈↓ ↓H␈↓found␈αwhich␈α
is␈αtrue.␈α Then␈α
the␈αcorresponding␈α␈↓∧e␈↓␈α
is␈αtaken␈α
as␈αthe␈αvalue␈α
of␈αthe␈αconditional␈α
expression.
␈↓ ↓H␈↓If␈αnone␈αof␈αthe␈α
␈↓∧p␈↓'s␈αis␈αtrue,␈αthen␈α
the␈αvalue␈αof␈αthe␈αconditional␈α
expression␈αis␈αundefined.␈α Thus␈α
all␈αthe
␈↓ ↓H␈↓␈↓∧e␈↓'s␈α⊗are␈α↔treated␈α⊗the␈α↔same␈α⊗which␈α⊗makes␈α↔programs␈α⊗for␈α↔interpreting␈α⊗or␈α↔compiling␈α⊗conditional
␈↓ ↓H␈↓expressions␈α
easier␈α
to␈α
write.␈α
 Putting␈α
parentheses␈α
around␈α
each␈α
␈↓∧p-e␈↓␈α
pair␈α
was␈α
probably␈α
a␈α
mistake␈αin
␈↓ ↓H␈↓the␈α
design␈αof␈α
LISP,␈αbecause␈α
it␈α
unnecessarily␈αincreases␈α
the␈αnumber␈α
of␈αright␈α
parentheses.␈α
 It␈αshould
␈↓ ↓H␈↓have␈αbeen␈α ␈↓∧(COND␈αp1␈αe1␈αp2␈αe2␈α...␈αpn␈αen)␈↓,␈αbut␈αsuch␈αa␈αchange␈αshould␈αbe␈αmade␈αnow␈αonly␈αas␈αpart␈αof␈αa
␈↓ ↓H␈↓massive improvement.

␈↓ ↓H␈↓        Conditional expressions may be compounded with functions to get forms like

␈↓ ↓H␈↓        ␈↓βif n ␈↓αx ␈↓βthen ␈↓∧NIL ␈↓βelse a ␈↓αx . append[␈↓βd ␈↓αx,y]␈↓

␈↓ ↓H␈↓involving a yet to be defined function ␈↓αappend␈↓.  The internal form of this is

␈↓ ↓H␈↓␈↓∧(COND ((NULL X) NIL) (T (CONS (CAR X) (APPEND (CDR X) Y))))␈↓.

␈↓ ↓H␈↓One␈αwould␈αnormally␈αhave␈αexpected␈αto␈αwrite␈α␈↓∧(QUOTE␈αNIL)␈↓␈αand␈α␈↓∧(QUOTE␈αT)␈↓,␈αbut␈αthere␈αis␈αa␈αspecial
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :11


␈↓ ↓H␈↓convention␈α
that␈α
␈↓∧NIL␈↓␈αand␈α
␈↓∧T␈↓␈α
may␈α
be␈αwritten␈α
without␈α
␈↓∧QUOTE␈↓.␈α
 This␈αmeans␈α
that␈α
these␈αsymbols␈α
cannot
␈↓ ↓H␈↓be␈αused␈α
as␈αvariables.␈α The␈α
value␈αof␈α␈↓∧T␈↓␈α
is␈αthe␈α
propositional␈αconstant␈α␈↓βtrue␈↓,␈α
i.e.␈αit␈αis␈α
always␈αtrue␈αso␈α
that
␈↓ ↓H␈↓it␈α∂is␈α⊂impossible␈α∂to␈α⊂"fall␈α∂off␈α∂the␈α⊂end"␈α∂of␈α⊂a␈α∂conditional␈α∂expression␈α⊂with␈α∂␈↓∧T␈↓␈α⊂as␈α∂its␈α∂last␈α⊂␈↓∧p␈↓.␈α∂ It␈α⊂is␈α∂the
␈↓ ↓H␈↓translation into internal form of the final ␈↓βelse␈↓ of a conditional expression.



␈↓ ↓H␈↓7.  ␈↓βBoolean expressions.␈↓


␈↓ ↓H␈↓        In␈α∩ making␈α∩ up␈α∪ the␈α∩ propositional␈α∩  parts␈α∩  of␈α∪  conditional␈α∩expressions,␈α∩  it␈α∪  is␈α∩  often
␈↓ ↓H␈↓necessary␈α∂  to␈α∞  combine␈α∂ elementary␈α∂propositional␈α∞expressions␈α∂using␈α∞the␈α∂Boolean␈α∂operators␈α∞ and,
␈↓ ↓H␈↓or,␈α
 and␈α
not.␈α
  We␈α
 use␈α the␈α
 symbols␈α
  ␈↓↓∧␈↓,␈α
 ␈↓↓∨␈↓,␈α
and␈α ␈↓↓¬␈↓␈α
 respectively,␈α
for␈α
these␈α
operators.␈α The␈α
Boolean
␈↓ ↓H␈↓operators␈αmay␈αbe␈αdescribed␈αsimply␈αby␈αlisting␈αthe␈αvalues␈αof␈αthe␈αelementary␈αBoolean␈αexpressions␈αfor
␈↓ ↓H␈↓each  case  of  the arguments.  Thus we have:

␈↓ ↓H␈↓        ␈↓∧T␈↓↓∧␈↓∧T ␈↓↓= ␈↓∧T
␈↓ ↓H␈↓∧␈↓        ␈↓∧T␈↓↓∧␈↓∧F ␈↓↓= ␈↓∧F
␈↓ ↓H␈↓∧␈↓        ␈↓∧F␈↓↓∧␈↓∧T ␈↓↓= ␈↓∧F
␈↓ ↓H␈↓∧␈↓        ␈↓∧F␈↓↓∧␈↓∧F ␈↓↓= ␈↓∧F

␈↓ ↓H␈↓∧␈↓        ␈↓∧T␈↓↓∨␈↓∧T ␈↓↓= ␈↓∧T
␈↓ ↓H␈↓∧␈↓        ␈↓∧T␈↓↓∨␈↓∧F ␈↓↓= ␈↓∧T
␈↓ ↓H␈↓∧␈↓        ␈↓∧F␈↓↓∨␈↓∧T ␈↓↓= ␈↓∧T
␈↓ ↓H␈↓∧␈↓        ␈↓∧F␈↓↓∨␈↓∧F ␈↓↓= ␈↓∧F

␈↓ ↓H␈↓∧␈↓        ␈↓∧␈↓↓¬␈↓∧T ␈↓↓= ␈↓∧F
␈↓ ↓H␈↓∧␈↓        ␈↓∧␈↓↓¬␈↓∧F ␈↓↓= ␈↓∧T.

␈↓ ↓H␈↓∧␈↓        ␈↓∧Since␈α⊂both␈α∂∧␈α⊂and␈α⊂∨␈α∂are␈α⊂associative␈α⊂we␈α∂can␈α⊂write␈α⊂Boolean␈α∂forms␈α⊂like␈α⊂␈↓αp1∧p2∧p3␈↓␈α∂without
␈↓ ↓H␈↓worrying␈α
about␈αgrouping.␈α
 The␈α
internal␈αforms␈α
are␈α␈↓∧(AND␈α
p1␈α
p2␈α...␈α
pn)␈↓,␈α␈↓∧(OR␈α
p1␈α
p2␈α...␈α
pn)␈↓␈α
and␈α␈↓∧(NOT
␈↓ ↓H␈↓∧p)␈↓.␈α It␈αis␈αalso␈αcustomary␈αto␈αuse␈α␈↓∧NIL␈↓␈αinstead␈αof␈α␈↓∧F␈↓,␈αbecause␈αin␈αmost␈αLISP␈αsystems␈αboth␈αBoolean␈α␈↓βfalse␈↓
␈↓ ↓H␈↓and␈α∩the␈α∩null␈α∩list␈α∩are␈α⊃represented␈α∩by␈α∩the␈α∩number␈α∩0.␈α⊃ This␈α∩makes␈α∩certain␈α∩tests␈α∩run␈α∩faster,␈α⊃but
␈↓ ↓H␈↓introduces so many complications in implementation that it was certainly a bad idea.

␈↓ ↓H␈↓        The␈α∞ Boolean␈α∂ operators␈α∞ can␈α∞ be␈α∂ described␈α∞ by␈α∞  conditional␈α∂expressions␈α∞in␈α∂the␈α∞following
␈↓ ↓H␈↓way:

␈↓ ↓H␈↓        ␈↓αp␈↓↓∧␈↓αq ␈↓↓= ␈↓βif ␈↓αp ␈↓βthen ␈↓αq ␈↓βelse ␈↓∧F
␈↓ ↓H␈↓∧␈↓        ␈↓∧␈↓αp␈↓↓∨␈↓αq ␈↓↓= ␈↓βif ␈↓αp ␈↓βthen ␈↓∧T ␈↓βelse ␈↓αq
␈↓ ↓H␈↓α␈↓        ␈↓α␈↓↓¬␈↓αp ␈↓↓= ␈↓βif ␈↓αp ␈↓βthen ␈↓∧F ␈↓βelse ␈↓∧T.

␈↓ ↓H␈↓∧␈↓Note␈αthat␈αif␈α ␈↓αp␈↓␈α is␈αfalse␈α ␈↓αp␈↓↓∧␈↓αq␈↓␈α is␈αfalse␈αindependent␈αof␈αthe␈αvalue␈α of␈α␈↓αq␈↓,␈α and␈α likewise␈α if␈α ␈↓αp␈↓␈α is␈αtrue,
␈↓ ↓H␈↓then␈α∞ ␈↓αp␈↓↓∨␈↓αq␈↓␈α∂ is␈α∞true␈α∞independent␈α∂of␈α∞␈↓αq␈↓.␈α∂ If␈α∞ ␈↓αp␈↓␈α∞ has␈α∂been␈α∞evaluated␈α∂and␈α∞found␈α∞to␈α∂be␈α∞false,␈α∂then␈α∞  ␈↓αq␈↓
␈↓ ↓H␈↓does␈α∂not␈α∂ have␈α⊂ to␈α∂ be␈α∂evaluated␈α⊂at␈α∂all␈α∂to␈α⊂find␈α∂the␈α∂value␈α⊂of␈α∂ ␈↓αp␈↓↓∧␈↓αq␈↓,␈α∂and,␈α⊂in␈α∂fact,␈α∂LISP␈α⊂does␈α∂not
␈↓ ↓H␈↓evaluate␈α
 ␈↓αq␈↓␈α
 in␈αthis␈α
case.␈α
 Similarly,␈α ␈↓αq␈↓␈α
 is␈α
not␈α
evaluated␈α in␈α
 evaluating␈α
  ␈↓αp␈↓↓∨␈↓αq␈↓␈α if␈α
 ␈↓αp␈↓␈α
 is␈α
true.␈αThis
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :12


␈↓ ↓H␈↓procedure␈α⊂is␈α⊃in␈α⊂accordance␈α⊃with␈α⊂the␈α⊂above␈α⊃conditional␈α⊂expression␈α⊃descriptions␈α⊂of␈α⊃ the␈α⊂Boolean
␈↓ ↓H␈↓operators.␈α The␈αimportance␈αof␈α
this␈αconvention␈αwhich␈αcontrasts␈αwith␈α
that␈αof␈αALGOL␈α 60,␈α
 will␈α be
␈↓ ↓H␈↓apparent  later  when  we  discuss recursive definitions of functions and predicates.

␈↓ ↓H␈↓        Boolean␈α
expressions␈α
can␈α
be␈α
combined␈α
with␈α
functions␈α
and␈α
conditional␈α
exrpessions␈α
to␈α
get␈α
forms
␈↓ ↓H␈↓like

␈↓ ↓H␈↓        ␈↓β if n ␈↓αx ∨ ␈↓βn d ␈↓α x ␈↓βthen ␈↓αx ␈↓βelse a ␈↓αx . alt ␈↓βdd ␈↓αx␈↓

␈↓ ↓H␈↓the internal form of which is

␈↓ ↓H␈↓    ␈↓∧(COND ((OR (NULL X) (NULL (CDR X))) X) (T (CONS (CAR X) (ALT (CDDR X)))))␈↓.



␈↓ ↓H␈↓8.  ␈↓βRecursive function definitions.␈↓


␈↓ ↓H␈↓        In␈α∞such␈α
languages␈α∞as␈α
FORTRAN␈α∞and␈α
 Algol,␈α∞ computer␈α
 progrrams␈α∞are␈α
 expressed␈α∞ in␈α
the
␈↓ ↓H␈↓main␈αas␈αsequences␈α
of␈αassignment␈αstatements␈αand␈α
conditional␈α␈↓βgo␈αto␈↓'s.␈α
 In␈αLISP,␈αprograms␈αare␈α
mainly
␈↓ ↓H␈↓expressed  in  the form of recursively defined functions.  We begin with an example.

␈↓ ↓H␈↓        The␈α∞ function␈α∞  ␈↓αalt␈↓↓[␈↓αx␈↓↓]␈↓␈α∞  gives␈α∞ a␈α∞ list␈α∂ whose␈α∞ elements␈α∞ are␈α∞alternate␈α∞elements␈α∞of␈α∞the␈α∂list␈α∞ ␈↓αx␈↓
␈↓ ↓H␈↓beginning with the first.  Thus

␈↓ ↓H␈↓        ␈↓αalt␈↓↓[␈↓∧(A B C D E)␈↓↓] = ␈↓∧(A C E),

␈↓ ↓H␈↓∧␈↓        ␈↓∧␈↓αalt␈↓↓[␈↓∧(((A B) (C D))␈↓↓] = ␈↓∧((A B)),

␈↓ ↓H␈↓∧␈↓        ␈↓∧␈↓αalt␈↓↓[␈↓∧(A)␈↓↓] = ␈↓∧(A),
␈↓ ↓H␈↓∧␈↓and
␈↓ ↓H␈↓        ␈↓αalt␈↓↓[␈↓∧NIL␈↓↓] = ␈↓∧NIL.

␈↓ ↓H␈↓∧␈↓        ␈↓∧We can define ␈↓αalt␈↓ by the equation

␈↓ ↓H␈↓    ␈↓αalt[x] ← ␈↓βif n ␈↓αx ∨ ␈↓βn d ␈↓αx ␈↓βthen ␈↓αx ␈↓βelse a ␈↓αx . alt[␈↓βdd ␈↓αx␈↓↓]␈↓.

␈↓ ↓H␈↓        This␈α
definition␈α
uses␈αno␈α
ways␈α
of␈αforming␈α
expressions␈α
that␈αwe␈α
haven't␈α
introduced␈αpreviously,
␈↓ ↓H␈↓but␈α
it␈α
uses␈α
the␈α
function␈α
␈↓αalt␈↓␈α
in␈α
the␈α
right␈α
hand␈α
side␈α
of␈α
its␈α
own␈α
defining␈α
equation.␈α
 To␈α
get␈α
the␈αvalue␈α
of
␈↓ ↓H␈↓␈↓αalt␈αx␈↓␈αfor␈αsome␈αparticular␈αlist,␈αwe␈αevaluate␈αthe␈αright␈αhand␈αside␈αof␈αthe␈αdefinition␈αsubstituting␈αthat␈α
list
␈↓ ↓H␈↓for␈α␈↓αx␈↓␈αwhenever␈α
␈↓αx␈↓␈αis␈αencountered␈α
and␈αre-evaluating␈αthe␈αright␈α
hand␈αside␈αwith␈α
a␈αnew␈α␈↓αx␈↓␈α
whenever␈αa
␈↓ ↓H␈↓form ␈↓αalt e␈↓ is encountered.

␈↓ ↓H␈↓        This␈α
process␈αis␈α
 best␈α
 explained␈α by␈α
 using␈α
 it␈αto␈α
evaluate␈α
some␈αexpressions.␈α
 However,␈αin␈α
case
␈↓ ↓H␈↓the reader has forgotten our precedence conventions, fully bracketed it looks like

␈↓ ↓H␈↓        ␈↓αalt[x] ← ␈↓βif ␈↓α[␈↓βn␈↓α[x] ∨ ␈↓βn␈↓α[␈↓βd␈↓α[x]]] ␈↓βthen␈↓α x ␈↓βelse␈↓α [␈↓βa␈↓α[x] . alt[␈↓βdd␈↓α[x]]]␈↓.
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :13


␈↓ ↓H␈↓Consider␈α
evaluating␈α
␈↓αalt[␈↓∧NIL␈↓↓]␈↓.␈α∞ We␈α
do␈α
it␈α
by␈α∞evaluating␈α
the␈α
expression␈α
to␈α∞the␈α
right␈α
of␈α
the␈α∞ ␈↓↓←␈↓␈α
 sign
␈↓ ↓H␈↓remembering␈αthat␈αthe␈αvariable␈α ␈↓αx␈↓␈α has␈αthe␈αvalue␈α ␈↓∧NIL␈↓.␈α A␈α conditional␈αexpression␈α is␈α evaluated␈αby
␈↓ ↓H␈↓first␈α⊂evaluating␈α⊂the␈α∂first␈α⊂propositional␈α⊂term␈α∂¬␈α⊂in␈α⊂this␈α∂case␈α⊂ ␈↓βn␈α⊂␈↓αx␈α∂␈↓↓∨␈α⊂␈↓βn␈α⊂d␈α∂␈↓αx␈↓.␈α⊂This␈α⊂expression␈α⊂is␈α∂a
␈↓ ↓H␈↓disjunction␈αand␈αin␈α its␈αevaluation␈αwe␈αfirst␈αevaluate␈αthe␈αfirst␈αdisjunct,␈αnamely␈α ␈↓βn ␈↓αx␈↓.␈α Since␈α ␈↓αx␈α␈↓↓=␈α␈↓∧NIL,
␈↓ ↓H␈↓∧␈↓βn␈α␈↓αx␈↓␈α is␈αtrue,␈αthe␈αdisjunction␈αis␈αtrue,␈αand␈αthe␈αvalue␈αof␈α the␈α conditional␈α expression␈α is␈α the␈αvalue␈αof
␈↓ ↓H␈↓the␈α∞term␈α
after␈α∞the␈α
first␈α∞true␈α
propositiional␈α∞term.␈α∞The␈α
term␈α∞is␈α
  ␈↓αx␈↓,␈α∞ and␈α
 its␈α∞ value␈α
 is␈α∞␈↓∧NIL␈↓,␈α∞ so␈α
the
␈↓ ↓H␈↓value␈α
of␈α
 ␈↓αalt␈↓↓[␈↓∧NIL␈↓↓]␈↓␈α∞ is␈α
 ␈↓∧NIL␈↓␈α
 as␈α
stated␈α∞above.␈α
  Obeying␈α
the␈α
rules␈α∞about␈α
the␈α
order␈α
of␈α∞evaluation␈α
of
␈↓ ↓H␈↓terms␈α∞in␈α∂ conditional␈α∞ and␈α∂Boolean␈α∞expressions␈α∂is␈α∞important␈α∂in␈α∞this␈α∂case␈α∞since␈α∂if␈α∞we␈α∂didn't␈α∞obey
␈↓ ↓H␈↓these␈αrules,␈αwe␈αmight␈αfind␈αourselves␈αtrying␈αto␈α evaluate␈α  ␈↓βn␈αd␈α␈↓αx␈↓␈α  or␈α␈↓αalt␈↓↓[␈↓βdd␈α␈↓αx␈↓↓]␈↓,␈αand␈αsince␈α ␈↓αx␈↓␈α
is␈α ␈↓∧NIL␈↓,
␈↓ ↓H␈↓neither␈α∞of␈α∞these␈α
has␈α∞a␈α∞value.␈α∞ An␈α
attempt␈α∞to␈α∞evaluate␈α
them␈α∞in␈α∞LISP␈α∞would␈α
give␈α∞rise␈α∞to␈α∞an␈α
error
␈↓ ↓H␈↓return.

␈↓ ↓H␈↓        As␈α
a␈αsecond␈α
example,␈αconsider␈α
  ␈↓αalt␈↓↓[␈↓∧(A␈α
 B)␈↓↓]␈↓.␈α  Since␈α
 neither␈α␈↓βn␈α
␈↓αx␈↓␈αnor␈α
␈↓βn␈α
d␈α␈↓αx␈↓␈α
is␈αtrue␈α
in␈αthis␈α
case,
␈↓ ↓H␈↓the␈αdisjunction␈α␈↓βn␈α␈↓αx␈α␈↓↓∨␈α␈↓βn␈αd␈α␈↓αx␈α␈↓is␈α false␈α and␈α the␈α value␈α of␈α the␈α expression␈α is␈α the␈α  value␈α  of␈α␈↓βa␈α␈↓αx␈α
.
␈↓ ↓H␈↓αalt␈↓↓[␈↓βdd␈α␈↓αx␈↓↓].␈α    ␈↓βa␈α␈↓αx␈↓␈αhas␈αthe␈αvalue␈α ␈↓∧A␈↓,␈αand␈α␈↓βdd␈α␈↓αx␈↓␈αhas␈αthe␈αvalue␈α␈↓∧NIL␈↓,␈αso␈αwe␈αmust␈αnow␈αevaluate␈α ␈↓αalt␈↓↓[␈↓∧NIL␈↓↓]␈↓,
␈↓ ↓H␈↓and␈α∞we␈α∞already␈α∞know␈α∞that␈α
the␈α∞value␈α∞  of␈α∞  this␈α∞  expression␈α
 is␈α∞  ␈↓∧NIL␈↓.␈α∞ Therefore,␈α∞ the␈α∞ value␈α
 of
␈↓ ↓H␈↓␈↓αalt␈↓↓[␈↓∧(A B)␈↓↓]␈↓  is that of  ␈↓∧A.NIL␈↓  which is  ␈↓∧(A)␈↓.

␈↓ ↓H␈↓        We can describe this  evaluation  in  a  less  wordy  way  by writing

␈↓ ↓H␈↓        ␈↓αalt␈↓↓[␈↓∧(A B)␈↓↓] = ␈↓βif n␈↓∧(A B) ␈↓↓∨ ␈↓βn d␈↓∧(A B) ␈↓βthen ␈↓∧(A B) ␈↓βelse
␈↓ ↓H␈↓β                        a␈↓∧(A B).␈↓αalt␈↓↓[␈↓βdd␈↓∧(A B)␈↓↓]

␈↓ ↓H␈↓↓                   = ␈↓βif ␈↓∧NIL ␈↓↓∨ ␈↓βn d␈↓∧(A B) ␈↓βthen ␈↓∧(A B) ␈↓βelse
␈↓ ↓H␈↓β                        a␈↓∧(A B).␈↓αalt␈↓↓[␈↓βdd␈↓∧(A B)␈↓↓]

␈↓ ↓H␈↓↓                   = ␈↓βif ␈↓∧NIL ␈↓βthen ␈↓∧(A B) ␈↓βelse
␈↓ ↓H␈↓β                        a␈↓∧(A B).␈↓αalt␈↓↓[␈↓βdd␈↓∧(A B)␈↓↓]

␈↓ ↓H␈↓↓                   = ␈↓βa␈↓∧(A B).␈↓αalt␈↓↓[␈↓βdd␈↓∧(A B)␈↓↓]

␈↓ ↓H␈↓↓                   = ␈↓∧A.␈↓αalt␈↓↓[␈↓∧NIL␈↓↓]

␈↓ ↓H␈↓↓                   = ␈↓∧A␈↓↓.[␈↓βif n␈↓∧NIL ␈↓↓∨ ␈↓βnd␈↓∧NIL ␈↓βthen ␈↓∧NIL ␈↓βelse
␈↓ ↓H␈↓β                        a␈↓∧NIL.␈↓αalt␈↓↓[␈↓βdd␈↓∧NIL␈↓↓]]

␈↓ ↓H␈↓↓                   = ␈↓∧A␈↓↓.[␈↓βif ␈↓∧T ␈↓↓∨ ␈↓βnd␈↓∧NIL ␈↓βthen ␈↓∧NIL ␈↓βelse
␈↓ ↓H␈↓β                        a␈↓∧NIL.␈↓αalt␈↓↓[␈↓βdd␈↓∧NIL␈↓↓]]

␈↓ ↓H␈↓↓                   = ␈↓∧A␈↓↓.[␈↓βif ␈↓∧T ␈↓βthen ␈↓∧NIL ␈↓βelse
␈↓ ↓H␈↓β                        a␈↓∧NIL.␈↓αalt␈↓↓[␈↓βdd␈↓∧NIL␈↓↓]]

␈↓ ↓H␈↓↓                   = ␈↓∧A␈↓↓.[␈↓∧NIL␈↓↓]

␈↓ ↓H␈↓↓                   = ␈↓∧(A).
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :14


␈↓ ↓H␈↓∧␈↓        ␈↓∧␈↓This␈α⊂is␈α⊂still␈α⊂very␈α⊂ long-winded,␈α⊂ and␈α⊂ now␈α⊂ that␈α⊂ the␈α⊂ reader␈α⊂understands␈α⊂ the␈α⊃ order␈α⊂ of
␈↓ ↓H␈↓evaluation  of  conditional  and Boolean expressions, we can proceed more briefly to evaluate

␈↓ ↓H␈↓        ␈↓αalt␈↓↓[␈↓∧(A B C D E)␈↓↓] = ␈↓∧A.␈↓αalt␈↓↓[␈↓∧(C D E)␈↓↓]

␈↓ ↓H␈↓↓                        = ␈↓∧A␈↓↓.[␈↓∧C.␈↓αalt␈↓↓[␈↓∧(E)␈↓↓]]

␈↓ ↓H␈↓↓                        = ␈↓∧A.␈↓↓[␈↓∧C.(E)␈↓↓]

␈↓ ↓H␈↓↓                        = ␈↓∧(A C E).

␈↓ ↓H␈↓∧␈↓        ␈↓∧␈↓Here␈α
are␈α
three␈α
more␈α
examples␈α
of␈αrecursive␈α
functions␈α
and␈α
their␈α
application:␈α
We␈α
define␈α ␈↓αlast␈↓
␈↓ ↓H␈↓by

␈↓ ↓H␈↓        ␈↓αlast␈↓↓[␈↓αx␈↓↓] ← ␈↓βif n d ␈↓αx ␈↓βthen a ␈↓αx ␈↓βelse ␈↓αlast␈↓↓[␈↓βd ␈↓αx␈↓↓],

␈↓ ↓H␈↓↓␈↓and we compute

␈↓ ↓H␈↓        ␈↓αlast␈↓↓[␈↓∧(A B C)␈↓↓] = ␈↓βif nd␈↓∧(A B C) ␈↓βthen a␈↓∧(A B C) ␈↓βelse ␈↓αlast␈↓↓[␈↓βd␈↓∧(A B C)␈↓↓]

␈↓ ↓H␈↓↓                      = ␈↓αlast␈↓↓[␈↓∧(B C)␈↓↓]

␈↓ ↓H␈↓↓                      = ␈↓αlast␈↓↓[␈↓∧(C)␈↓↓]

␈↓ ↓H␈↓↓                      = ␈↓∧C.

␈↓ ↓H␈↓∧␈↓Clearly␈α
  ␈↓αlast␈↓␈α
  computes␈α the␈α
 last␈α
element␈αof␈α
a␈α
list.␈α ␈↓αlast␈↓↓[␈↓∧NIL␈↓↓]␈↓␈α
is␈α
undefined␈αin␈α
the␈α
LISP␈αlanguage;
␈↓ ↓H␈↓the␈α⊃result␈α⊂of␈α⊃trying␈α⊂ to␈α⊃ compute␈α⊂ it␈α⊃may␈α⊂be␈α⊃an␈α⊂error␈α⊃message␈α⊂or␈α⊃may␈α⊂be␈α⊃some␈α⊃random␈α⊂result
␈↓ ↓H␈↓depending on the implementation.

␈↓ ↓H␈↓        The function  ␈↓αsubst␈↓  is defined by

␈↓ ↓H␈↓        ␈↓αsubst␈↓↓[␈↓αx, y, z␈↓↓] ← ␈↓βif at ␈↓αz ␈↓βthen ␈↓↓[␈↓βif ␈↓αz ␈↓βeq ␈↓αy ␈↓βthen ␈↓αx ␈↓βelse ␈↓αz␈↓↓] ␈↓βelse ␈↓αsubst[x,y,␈↓βa ␈↓αz].subst[x,y,␈↓βd ␈↓αz]␈↓.

␈↓ ↓H␈↓We have

␈↓ ↓H␈↓        ␈↓αsubst␈↓↓[␈↓∧(A.B), X, ((X.A).X)␈↓↓] =

␈↓ ↓H␈↓↓␈↓                ␈↓↓= ␈↓αsubst␈↓↓[␈↓∧(A.B), X, (X.A)␈↓↓]␈↓αsubst␈↓↓[␈↓∧(A.B), X, X␈↓↓]

␈↓ ↓H␈↓↓␈↓                ␈↓↓= [␈↓αsubst␈↓↓[␈↓∧(A.B), X, X␈↓↓].␈↓αsubst␈↓↓[␈↓∧(A.B), X, A␈↓↓]].␈↓∧(A.B)

␈↓ ↓H␈↓∧␈↓                ␈↓∧␈↓↓= [[␈↓∧(A.B)␈↓↓].␈↓∧A␈↓↓].␈↓∧(A.B)␈↓↓]

␈↓ ↓H␈↓↓␈↓                ␈↓↓= ␈↓∧(((A.B).A).(A.B)).
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :15


␈↓ ↓H␈↓∧␈↓αsubst␈↓␈α∩ computes␈α∪the␈α∩result␈α∪of␈α∩substituting␈α∪the␈α∩S-expression␈α∪  ␈↓αx␈↓␈α∩  for␈α∪the␈α∩ atom␈α∪ ␈↓αy␈↓␈α∩ in␈α∪the␈α∩S-
␈↓ ↓H␈↓expression  ␈↓αz␈↓.  This operation is important in all kinds of symbolic computation.

␈↓ ↓H␈↓        The␈α∩function␈α∩␈↓αappend[x,y]␈↓␈α∩which␈α∩gives␈α∩the␈α∪ concatenation␈α∩ of␈α∩the␈α∩lists␈α∩␈↓αx␈↓␈α∩and␈α∩␈↓αx␈↓␈α∪is␈α∩also
␈↓ ↓H␈↓importan.␈α
 It␈α
is␈α
also␈α
denoted␈α
by␈α
the␈α
infixed␈αexpression␈α
 ␈↓αx␈↓↓*␈↓αy␈↓␈α
 since␈α
it␈α
is␈α
associative.␈α
 We␈α
have␈αthe
␈↓ ↓H␈↓examples

␈↓ ↓H␈↓        ␈↓∧(A B C)␈↓↓*␈↓∧(D E F) ␈↓↓= ␈↓∧(A B C D E F),

␈↓ ↓H␈↓∧␈↓and

␈↓ ↓H␈↓        ␈↓∧NIL␈↓↓*␈↓∧(A B) ␈↓↓= ␈↓∧(A B) ␈↓↓= ␈↓∧(A B)␈↓↓*␈↓∧NIL,

␈↓ ↓H␈↓∧␈↓and the formal definition

␈↓ ↓H␈↓        ␈↓αx␈↓↓*␈↓αy ␈↓↓← ␈↓βif n ␈↓αx ␈↓βthen ␈↓αy ␈↓βelse ␈↓↓[␈↓βa ␈↓αx].[[␈↓βd ␈↓αx␈↓↓]*␈↓αy␈↓↓].

␈↓ ↓H␈↓↓␈↓        ␈↓↓␈↓The␈α∂ Boolean␈α∂ operations␈α∂can␈α∞also␈α∂be␈α∂used␈α∂in␈α∞making␈α∂recursive␈α∂definitions␈α∂ provided␈α∞ we
␈↓ ↓H␈↓observe  the  order   of   evaluation   of constituents. First, we define a predicate  ␈↓αequal␈↓  by

␈↓ ↓H␈↓        ␈↓αequal[x,y] ← x ␈↓βeq ␈↓αy ∨ [¬␈↓βat ␈↓αx ∧ ¬␈↓βat ␈↓αy ∧ equal[␈↓βa ␈↓αx,␈↓βa ␈↓αy] ∧ equal[␈↓βd ␈↓αx, ␈↓βd ␈↓αy]]␈↓.

␈↓ ↓H␈↓␈↓αequal[x,y]␈↓␈αis␈αtrue␈αif␈αand␈αonly␈αif␈α  ␈↓αx␈↓␈α  and␈α  ␈↓αy␈↓␈α  are␈α the␈α same␈αS-expression,␈α and␈α the␈α use␈α of␈αthis
␈↓ ↓H␈↓predicate␈αmakes␈αup␈αfor␈αthe␈αfact␈αthat␈α
the␈αbasic␈αpredicate␈α ␈↓βeq␈↓␈α is␈αguaranteed␈α to␈α test␈α
 equality␈α only
␈↓ ↓H␈↓when  one  of the operands is known to be an atom.  We shall also use the infixes  ␈↓↓=␈↓  and  ␈↓↓≠␈↓.

␈↓ ↓H␈↓        Membership of an S-expression  ␈↓αx␈↓  in a list  ␈↓αy␈↓  is tested by

␈↓ ↓H␈↓        ␈↓αmember␈↓↓[␈↓αx, y␈↓↓] ← ¬␈↓βn ␈↓αy ␈↓↓∧ [[␈↓αx ␈↓↓= ␈↓βa ␈↓αy␈↓↓] ∨ ␈↓αmember␈↓↓[␈↓αx, ␈↓βd ␈↓αy␈↓↓]].

␈↓ ↓H␈↓↓␈↓This relation is also denoted by  ␈↓αx␈↓↓ε␈↓αy.  Here are some computations:

␈↓ ↓H␈↓α␈↓        ␈↓αmember␈↓↓[␈↓∧B, (A B)␈↓↓] = ¬␈↓βn ␈↓∧(A B) ␈↓↓∧ [[␈↓∧B ␈↓↓= ␈↓βa ␈↓∧(A B)␈↓↓]
␈↓ ↓H␈↓↓                            ∨ ␈↓αmember␈↓↓[␈↓∧B, ␈↓βd ␈↓∧(A B)␈↓↓]],

␈↓ ↓H␈↓↓                        = ␈↓αmember␈↓↓[␈↓∧B, (B)␈↓↓]

␈↓ ↓H␈↓↓                        = ␈↓∧T.

␈↓ ↓H␈↓∧␈↓        ␈↓∧␈↓Sometimes␈α a␈α function␈α is␈α
defined␈αwith␈αthe␈αhelp␈αof␈α
auxiliary␈αfunctions.␈α Thus,␈αthe␈αreverse␈α
of
␈↓ ↓H␈↓a list  ␈↓αx␈↓ , (e.g.   ␈↓αreverse␈↓↓[␈↓∧(A B C D)␈↓↓] = ␈↓∧(D C B A)␈↓), is given by

␈↓ ↓H␈↓        ␈↓αreverse␈↓↓[␈↓αx␈↓↓] ← ␈↓αrev␈↓↓[␈↓αx, ␈↓∧NIL␈↓↓]

␈↓ ↓H␈↓↓␈↓where

␈↓ ↓H␈↓        ␈↓αrev␈↓↓[␈↓αx, y␈↓↓]   ← ␈↓βif n ␈↓αx ␈↓βthen ␈↓αy ␈↓βelse ␈↓αrev␈↓↓[␈↓βd ␈↓αx␈↓↓, [␈↓βa ␈↓αx␈↓↓].␈↓αy␈↓↓].
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :16


␈↓ ↓H␈↓↓␈↓A computation is

␈↓ ↓H␈↓        ␈↓αreverse␈↓↓[␈↓∧(A B C)␈↓↓] = ␈↓αrev␈↓↓[␈↓∧(A B C), NIL␈↓↓]

␈↓ ↓H␈↓↓                         = ␈↓αrev␈↓↓[␈↓∧(B C), (A)␈↓↓]

␈↓ ↓H␈↓↓                         = ␈↓αrev␈↓↓[␈↓∧(C), (B A)␈↓↓]

␈↓ ↓H␈↓↓                         = ␈↓αrev␈↓↓[␈↓∧NIL, (C B A)␈↓↓]

␈↓ ↓H␈↓↓                         = ␈↓∧(C B A).

␈↓ ↓H␈↓∧␈↓        ␈↓∧␈↓A more elaborate example of recursive definition is given by

␈↓ ↓H␈↓        ␈↓αflatten␈↓↓[␈↓αx␈↓↓] ← ␈↓αflat␈↓↓[␈↓αx, ␈↓∧NIL␈↓↓]

␈↓ ↓H␈↓↓␈↓        ␈↓↓␈↓αflat␈↓↓[␈↓αx, y␈↓↓] ← ␈↓βif at ␈↓αx ␈↓βthen ␈↓αx.y
␈↓ ↓H␈↓α                              ␈↓βelse ␈↓αflat␈↓↓[␈↓βa ␈↓αx, flat␈↓↓[␈↓βd ␈↓αx, y␈↓↓]].

␈↓ ↓H␈↓↓␈↓We have

␈↓ ↓H␈↓        ␈↓αflatten␈↓↓[␈↓∧((A.B).C)␈↓↓] = ␈↓αflat␈↓↓[␈↓∧((A.B).C), NIL␈↓↓]

␈↓ ↓H␈↓↓                           = ␈↓αflat␈↓↓[␈↓∧(A.B), ␈↓αflat␈↓↓[␈↓∧C, NIL␈↓↓]]

␈↓ ↓H␈↓↓                           = ␈↓αflat␈↓↓[␈↓∧(A.B), (C)␈↓↓]

␈↓ ↓H␈↓↓                           = ␈↓αflat␈↓↓[␈↓∧A, ␈↓αflat␈↓↓[␈↓∧B, (C)␈↓↓]]

␈↓ ↓H␈↓↓                           = ␈↓αflat␈↓↓[␈↓∧A, (B C)␈↓↓]

␈↓ ↓H␈↓↓                           = ␈↓∧(A B C).

␈↓ ↓H␈↓∧␈↓The␈α reader␈α
 will␈αsee␈αthat␈α
the␈αvalue␈α
of␈α ␈↓αflatten␈↓↓[␈↓αx␈↓↓]␈↓␈α is␈α
a␈αlist␈α
of␈αthe␈αatoms␈α
 of␈α the␈α
 S-expression␈α  ␈↓αx␈↓
␈↓ ↓H␈↓from   left   to   write.    Thus ␈↓αflatten␈↓↓[␈↓∧((A B) A)␈↓↓] = ␈↓∧(A B NIL A NIL)␈↓.

␈↓ ↓H␈↓        Many␈α⊃ functions␈α⊃ can␈α⊃be␈α⊃conveniently␈α⊃written␈α⊃in␈α⊃more␈α⊃than␈α⊃one␈α⊃way.␈α⊃ For␈α⊃example,␈α⊂the
␈↓ ↓H␈↓function   ␈↓αreverse␈↓   mentioned  above  can  be written without an auxiliary function as follows:

␈↓ ↓H␈↓        ␈↓αreverse␈↓↓[␈↓αx␈↓↓] ← ␈↓βif n ␈↓αx ␈↓βthen ␈↓∧NIL ␈↓βelse ␈↓αreverse␈↓↓[␈↓βd ␈↓αx␈↓↓]*␈↓∧<a x>

␈↓ ↓H␈↓∧␈↓but it will be explained later that the earlier  definition  involves less computation.

␈↓ ↓H␈↓        The␈α∞use␈α∞of␈α∞conditional␈α
 expressions␈α∞ for␈α∞ recursive␈α∞ function␈α
definition␈α∞ is␈α∞ not␈α∞ limited␈α
 to
␈↓ ↓H␈↓functions␈α of␈α S-expressions.␈α
  For␈αexample,␈αthe␈α
factorial␈αfunction␈αand␈α
the␈αEuclidean␈αalgorithm␈α
 for
␈↓ ↓H␈↓the greatest common divisor are expressed as follows:
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :17


␈↓ ↓H␈↓        ␈↓αn␈↓↓! ← ␈↓βif ␈↓αn␈↓↓=␈↓∧0 ␈↓βthen ␈↓∧1 ␈↓βelse ␈↓αn␈↓↓(␈↓αn␈↓↓-␈↓∧1␈↓↓)!

␈↓ ↓H␈↓↓␈↓and

␈↓ ↓H␈↓        ␈↓αgcd␈↓↓(␈↓αm, n␈↓↓) ← ␈↓βif ␈↓αm␈↓↓>␈↓αn ␈↓βthen ␈↓αgcd␈↓↓(␈↓αn, m␈↓↓) ␈↓βelse if ␈↓αm␈↓↓=␈↓∧0 ␈↓βthen ␈↓αn
␈↓ ↓H␈↓α                        ␈↓βelse ␈↓αgcd␈↓↓(␈↓αn mod m, m␈↓↓)

␈↓ ↓H␈↓↓␈↓where␈α
 ␈↓αn␈α
mod␈α
m␈↓␈α
 denotes␈αthe␈α
remainder␈α
when␈α
 ␈↓αn␈↓␈α
 is␈α
divided␈αby␈α
 ␈↓αm␈↓␈α
  and␈α
may␈α
itself␈α
be␈αexpressed
␈↓ ↓H␈↓recursively by

␈↓ ↓H␈↓        ␈↓αn mod m ␈↓↓← ␈↓βif ␈↓αn␈↓↓<␈↓αm ␈↓βthen ␈↓αn ␈↓βelse ␈↓↓(␈↓αn␈↓↓-␈↓αm␈↓↓) ␈↓αmod m.

␈↓ ↓H␈↓α␈↓        ␈↓αThe␈α
internal␈αform␈α
of␈αfunction␈α
definitions␈α
depends␈αon␈α
the␈αimplementation.␈α
 Stanford␈αLISP␈α
and
␈↓ ↓H␈↓αUCI LISP for the PDP-10 computer use the form

␈↓ ↓H␈↓α␈↓        ␈↓α␈↓∧(DE <function name> <list of variables> <right hand side>)␈↓.

␈↓ ↓H␈↓In these LISPS, the above definition of ␈↓αsubst␈↓ is

␈↓ ↓H␈↓        ␈↓∧(DE␈αSUBST␈α(X␈αY␈αZ)␈α(COND␈α((ATOM␈αZ)␈α(COND␈α((EQ␈αZ␈αX)␈αY)␈α(T␈αZ)))␈α(T␈α(CONS␈α(SUBST␈αX
␈↓ ↓H␈↓∧Y (CAR Z)) (SUBST X Y (CDR Z))))))␈↓,

␈↓ ↓H␈↓and the definition of ␈↓αalt␈↓ is

␈↓ ↓H␈↓        ␈↓∧(DE␈αALT␈α(X)␈α(COND␈α((OR␈α(NULL␈αX)␈α(NULL␈α(CDR␈αX)))␈αX)␈α(T␈α(CONS␈α(CAR␈αX)␈α(ALT␈α(CDDR
␈↓ ↓H␈↓∧X))))))␈↓.

␈↓ ↓H␈↓                              Exercises

␈↓ ↓H␈↓        1. Consider the function  ␈↓αdrop␈↓  defined by

␈↓ ↓H␈↓        ␈↓αdrop␈↓↓[␈↓αx␈↓↓] ← ␈↓βif n ␈↓αx ␈↓βthen ␈↓∧NIL ␈↓βelse ␈↓↓<␈↓βa ␈↓αx␈↓↓>.␈↓αdrop␈↓↓[␈↓βd ␈↓αx␈↓↓].

␈↓ ↓H␈↓↓␈↓Compute (by hand)  ␈↓αdrop␈↓↓[␈↓∧(A B C)␈↓↓]␈↓.  What does  ␈↓αdrop␈↓  do  to  lists  in general?

␈↓ ↓H␈↓        2. What does the function

␈↓ ↓H␈↓        ␈↓αr2␈↓↓[␈↓αx␈↓↓] ← ␈↓βif n ␈↓αx ␈↓βthen ␈↓∧NIL ␈↓βelse ␈↓αreverse␈↓↓[␈↓βa ␈↓αx␈↓↓].␈↓αr2␈↓↓[␈↓βd ␈↓αx␈↓↓]

␈↓ ↓H␈↓↓␈↓do to lists of lists?  How about

␈↓ ↓H␈↓        ␈↓αr3␈↓↓[␈↓αx␈↓↓] ← ␈↓βif at ␈↓αx ␈↓βthen ␈↓αx ␈↓βelse ␈↓αreverse␈↓↓[␈↓αr4␈↓↓[␈↓αx␈↓↓]]

␈↓ ↓H␈↓↓␈↓        ␈↓↓␈↓αr4␈↓↓[␈↓αx␈↓↓] ← ␈↓βif n ␈↓αx ␈↓βthen ␈↓∧NIL ␈↓βelse ␈↓αr3␈↓↓[␈↓βa ␈↓αx␈↓↓].␈↓αr4␈↓↓[␈↓βd ␈↓αx␈↓↓]?

␈↓ ↓H␈↓↓␈↓        ␈↓↓␈↓3. Compare
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :18


␈↓ ↓H␈↓        ␈↓αr3'␈↓↓[␈↓αx␈↓↓] ← ␈↓βif at ␈↓αx ␈↓βthen ␈↓αx ␈↓βelse ␈↓αr3'␈↓↓[␈↓βd ␈↓αx␈↓↓]*<␈↓αr3'␈↓↓[␈↓βa ␈↓αx␈↓↓]>

␈↓ ↓H␈↓↓␈↓with the function  ␈↓αr3␈↓  of the preceding example.

␈↓ ↓H␈↓        4. Consider  ␈↓αr5␈↓  defined by

␈↓ ↓H␈↓        ␈↓αr5␈↓↓[␈↓αx␈↓↓] ← ␈↓βif n ␈↓αx ␈↓↓∨ ␈↓βn d ␈↓αx ␈↓βthen ␈↓αx
␈↓ ↓H␈↓α␈↓                ␈↓α␈↓βelse ␈↓↓[␈↓βa ␈↓αr5␈↓↓[␈↓βd ␈↓αx␈↓↓]]
␈↓ ↓H␈↓↓                        . ␈↓αr5␈↓↓[␈↓βa ␈↓αx . r5␈↓↓[␈↓βd ␈↓αr5␈↓↓[␈↓βd ␈↓αx␈↓↓]]].

␈↓ ↓H␈↓↓␈↓Compute␈α ␈↓αr5␈↓↓[␈↓∧(A␈αB␈αC␈αD)␈↓↓]␈↓.␈α What␈αdoes␈α ␈↓∧r5␈↓␈α do␈αin␈αgeneral?␈α  Needless␈α to␈αsay,␈αthis␈αis␈αnot␈αa␈αgood␈αway
␈↓ ↓H␈↓of computing this function even though it involves no auxiliary functions.



␈↓ ↓H␈↓9.  ␈↓βLambda expressions and functions with functions as arguments.␈↓


␈↓ ↓H␈↓        It␈α
is␈α
common␈α
to␈α
use␈α
phrases␈α
like␈α
"the␈α
function␈α
 2␈↓αx␈↓↓+␈↓αy␈↓".␈α
  This␈α
is␈α
 not␈α
a␈α
precise␈αnotation␈α
because
␈↓ ↓H␈↓we␈α∃cannot␈α∃say␈α∃ 2␈↓αx␈↓↓+␈↓αy␈↓↓(␈↓∧3,␈α∃4␈↓↓)␈↓␈α∃ and␈α∃know␈α∀whether␈α∃the␈α∃desired␈α∃ result␈α∃ is␈α∃  2␈↓
␈␈↓3+4␈α∃  or␈α∀  2␈↓
␈␈↓4+3
␈↓ ↓H␈↓regarding␈α the␈αexpression␈α as␈αa␈αfunction␈αof␈αtwo␈αvariables.␈α Worse␈αyet,␈αwe␈αmight␈αhave␈αmeant␈αa␈αone-
␈↓ ↓H␈↓variable function of  ␈↓αx␈↓  wherein  ␈↓αy␈↓   is  regarded  as  a parameter.

␈↓ ↓H␈↓        The␈α∂problem␈α∂ of␈α∂ giving␈α∂ names␈α∂ to␈α∞ functions␈α∂ is␈α∂ solved␈α∂ by␈α∂Church's␈α∂  λ-notation.␈α∞   In
␈↓ ↓H␈↓the␈α∂ above␈α∂ example,␈α∂ we␈α∂ would␈α∂ write␈α∂␈↓↓λ␈↓αx␈α⊂y␈↓↓:␈α∂␈↓∧2␈↓αx␈↓↓+␈↓αy␈↓␈α∂ to␈α∂denote␈α∂ the␈α∂ function␈α∂ of␈α⊂ two␈α∂ variables
␈↓ ↓H␈↓with␈α first␈αargument␈α  ␈↓αx␈↓␈α  and␈α second␈α argument␈α
  ␈↓αy␈↓␈α whose␈αvalue␈αis␈αgiven␈αby␈αthe␈αexpression␈α
 2␈↓αx␈↓↓+␈↓αy␈↓.
␈↓ ↓H␈↓Thus,

␈↓ ↓H␈↓        ␈↓↓[λ␈↓αx y␈↓↓: ␈↓∧2␈↓αx␈↓↓+␈↓αy␈↓↓][␈↓∧3, 4␈↓↓] = ␈↓∧10␈↓.

␈↓ ↓H␈↓Likewise,␈α∩  ␈↓↓[λ␈↓αy␈α⊃x␈↓↓:␈α∩␈↓∧2␈↓αx␈↓↓+␈↓αy␈↓↓][␈↓∧3,␈α⊃4␈↓↓]␈α∩=␈α⊃␈↓∧11␈↓.␈α∩ Like␈α⊃variables␈α∩of␈α⊃integration␈α∩and␈α⊃the␈α∩bound␈α∩variables␈α⊃of
␈↓ ↓H␈↓quantifiers␈αin␈α
logic,␈αvariables␈α
following␈α  λ␈α
are␈α bound␈α
 or␈αdummy␈α
and␈αthe␈α
expression␈αas␈α
a␈αwhole
␈↓ ↓H␈↓may␈α
be␈α∞replaced␈α
by␈α
any␈α∞others␈α
provided␈α
the␈α∞replacement␈α
is␈α
done␈α∞consistently␈α
and␈α
does␈α∞not␈α
make
␈↓ ↓H␈↓any␈α∂ variable␈α∞ bound␈α∂ by␈α∂ λ␈α∞ the␈α∂same␈α∂as␈α∞a␈α∂free␈α∂variable␈α∞in␈α∂the␈α∂expression.␈α∞ Thus␈α∂  ␈↓↓λ␈↓αx␈α∂y␈↓↓:␈α∞␈↓∧2␈↓αx␈↓↓+␈↓αy␈↓
␈↓ ↓H␈↓represents␈α the␈α same␈α
  function␈α  as␈α␈↓↓λ␈↓αy␈αx␈↓↓:␈α
␈↓∧2␈↓αy␈↓↓+␈↓αx␈↓␈αor␈α␈↓↓λ␈↓αu␈αv␈↓↓:␈α
␈↓∧2␈↓αu␈↓↓+␈↓αv␈↓␈α,␈αbut␈αin␈α
the␈αfunction␈αof␈αone␈α
argument
␈↓ ↓H␈↓␈↓↓λ␈↓αx␈↓↓: ␈↓∧2␈↓αx␈↓↓+␈↓αy␈↓ , we cannot replace the variable  ␈↓αx␈↓  by ␈↓αy␈↓ , though we could replace it by  ␈↓αu␈↓.

␈↓ ↓H␈↓        λ-notation␈αplays␈αtwo␈αimportant␈α roles␈α in␈α LISP.␈α  First,␈α it␈αallows␈αus␈αto␈αrewrite␈αan␈αexpression
␈↓ ↓H␈↓containing␈αtwo␈αor␈αmore␈αoccurrences␈αof␈αthe␈αsame␈αsub-expression␈αin␈αsuch␈αa␈αway␈αthat␈αthe␈α expression
␈↓ ↓H␈↓occurs␈α∪only␈α∪once.␈α∪Thus␈α∪  ␈↓↓(␈↓∧2␈↓αx␈↓↓+␈↓∧1␈↓↓)␈↓ε4␈↓↓+␈↓∧3␈↓↓(␈↓∧2␈↓αx␈↓↓+␈↓∧1␈↓↓)␈↓ε3␈↓␈α∪ can␈α∪be␈α∪written␈α∪␈↓↓[λ␈↓αw␈↓↓:␈α∪␈↓αw␈↓ε4␈↓↓+␈↓∧3␈↓αw␈↓ε3␈↓↓][␈↓∧2␈↓αx␈↓↓+␈↓∧1␈↓↓]␈↓.␈α∪This␈α∀can␈α∪save
␈↓ ↓H␈↓considerable␈αcomputation,␈α
and␈αcorresponds␈α
to␈αthe␈αpractice␈α
in␈αordinary␈α
programming␈αof␈αassigning␈α
to
␈↓ ↓H␈↓a␈αvariable␈αthe␈αvalue␈αof␈αa␈αsub-expression␈αthat␈αoccurs␈αmore␈αthan␈αonce␈α in␈αan␈α expression␈α and␈α then
␈↓ ↓H␈↓writing  the  expression  in  terms of the variable.

␈↓ ↓H␈↓        The␈α∞second␈α∞use␈α∞of␈α∞λ-expressions␈α∞is␈α∂in␈α∞ using␈α∞ functions␈α∞ that␈α∞take␈α∞functions␈α∂as␈α∞arguments.
␈↓ ↓H␈↓Suppose␈αwe␈α
want␈αto␈αform␈α
a␈αnew␈αlist␈α
from␈αan␈αold␈α
one␈αby␈αapplying␈α
a␈αfunction␈α ␈↓αf␈↓␈α
 to␈αeach␈αelement␈α
 of
␈↓ ↓H␈↓the  list.  This can be done using the function  ␈↓αmapcar␈↓  defined by
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :19


␈↓ ↓H␈↓        ␈↓αmapcar␈↓↓[␈↓αx, f␈↓↓] ← ␈↓βif n ␈↓αx ␈↓βthen ␈↓∧NIL ␈↓βelse ␈↓αf␈↓↓[␈↓βa ␈↓αx␈↓↓]  . ␈↓αmapcar␈↓↓[␈↓βd ␈↓αx, f␈↓↓].

␈↓ ↓H␈↓↓␈↓Suppose␈α
the␈αoperation␈α
we␈αwant␈α
to␈αperform␈α
is␈α
squaring,␈αand␈α
we␈αwant␈α
 to␈αapply␈α
it␈α
to␈αthe␈α
list␈α ␈↓∧(1␈α
2␈α3␈α
4
␈↓ ↓H␈↓∧5 6 7)␈↓.  We have

␈↓ ↓H␈↓        ␈↓αmapcar␈↓↓[␈↓∧(1 2 3 4 5 6 7), ␈↓↓λ␈↓αx␈↓↓: ␈↓αx␈↓ε2␈↓↓] = ␈↓∧(1 4 9 16 25 36 49).

␈↓ ↓H␈↓∧␈↓        ␈↓∧␈↓A␈α
more␈α
generally␈α
useful␈α
operation␈α
than␈α
 ␈↓αmapcar␈↓␈α
is␈α
␈↓αmaplist␈↓␈α
in␈α
 which␈α
 the␈α
 function␈α
is␈α
applied
␈↓ ↓H␈↓to the successive sublists of the list rather than to the elements.  ␈↓αmaplist␈↓  is defined by

␈↓ ↓H␈↓        ␈↓αmaplist␈↓↓[␈↓αx, f␈↓↓] ← ␈↓βif n ␈↓αx ␈↓βthen ␈↓∧NIL ␈↓βelse ␈↓αf␈↓↓[␈↓αx␈↓↓]  . ␈↓αmaplist␈↓↓[␈↓βd ␈↓αx, f␈↓↓].

␈↓ ↓H␈↓↓␈↓        ␈↓↓␈↓As␈α∞ an␈α∞ application␈α∞ of␈α∞ ␈↓αmaplist␈↓␈α∞and␈α∞functional␈α∞arguments,␈α∞we␈α∞shall␈α∞define␈α∞a␈α∂function␈α∞ for
␈↓ ↓H␈↓differentiating␈α algebraic␈α expressions␈αinvolving␈αsums␈αand␈αproducts.␈α The␈αexpressions␈αare␈αbuilt␈αup
␈↓ ↓H␈↓from atoms denoting variables and integer constants according to the syntax

␈↓ ↓H␈↓        <expression> ::= <variable> | <integer> |
␈↓ ↓H␈↓                         (PLUS <explist>) | (TIMES <explist>)

␈↓ ↓H␈↓        <explist>    ::= <expression> | <expression><explist>

␈↓ ↓H␈↓Here,␈α∂ ␈↓∧PLUS␈↓␈α⊂ followed␈α∂by␈α⊂a␈α∂list␈α⊂of␈α∂arguments␈α⊂denotes␈α∂the␈α⊂sum␈α∂of␈α⊂these␈α∂arguments␈α⊂and␈α∂ ␈↓∧TIMES␈↓
␈↓ ↓H␈↓followed␈α⊂by␈α⊃a␈α⊂list␈α⊂of␈α⊃arguments␈α⊂ denotes␈α⊂ their␈α⊃product.␈α⊂  The␈α⊂ function␈α⊃  ␈↓αdiff␈↓↓[␈↓αe,␈α⊂v␈↓↓]␈↓␈α⊃ gives␈α⊂the
␈↓ ↓H␈↓partial derivative of the expression  ␈↓αe␈↓  with respect to the variable  ␈↓αv␈↓. We have

␈↓ ↓H␈↓        ␈↓αdiff␈↓↓[␈↓αe, v␈↓↓] ← ␈↓βif at ␈↓αe ␈↓βthen ␈↓↓[␈↓βif ␈↓αe ␈↓βeq ␈↓αv ␈↓βthen ␈↓∧1 ␈↓βelse ␈↓∧0␈↓↓]
␈↓ ↓H␈↓↓␈↓                ␈↓↓␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧PLUS ␈↓βthen
␈↓ ↓H␈↓β                        ␈↓∧PLUS . ␈↓αmapcar␈↓↓[␈↓βd ␈↓αe␈↓↓, λ␈↓αx␈↓↓: ␈↓αdiff␈↓↓[␈↓αx, v␈↓↓]_]
␈↓ ↓H␈↓↓␈↓                ␈↓↓␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧TIMES ␈↓αthen
␈↓ ↓H␈↓α                        ␈↓∧PLUS.␈↓αmaplist␈↓↓[␈↓βd ␈↓αe␈↓↓, λ␈↓αx␈↓↓: ␈↓∧TIMES
␈↓ ↓H␈↓∧                              . ␈↓αmaplist␈↓↓[␈↓βd ␈↓αe␈↓↓, λ␈↓αy␈↓↓: ␈↓βif ␈↓αx ␈↓βeq ␈↓αy ␈↓βthen
␈↓ ↓H␈↓β                                        ␈↓αdiff␈↓↓[␈↓βa ␈↓αy, v␈↓↓] ␈↓βelse a ␈↓αy␈↓↓]].

␈↓ ↓H␈↓↓␈↓The  term  that  describes  the  rule  for  differentiating  products corresponds to the rule

␈↓ ↓H␈↓        ␈↓↓∂/∂␈↓αv    e␈↓¬i␈↓↓ =       [␈↓βif ␈↓αi␈↓↓=␈↓αj ␈↓βthen ␈↓↓∂␈↓αe␈↓¬j␈↓↓/∂␈↓αv ␈↓βelse ␈↓αe␈↓¬j␈↓↓].


␈↓ ↓H␈↓↓and␈α  ␈↓αmaplist␈↓␈α  has␈α to␈αbe␈αused␈αrather␈α
than␈α ␈↓αmapcar␈↓␈α since␈αwhether␈αto␈αdifferentiate␈αin␈α
forming␈αthe
␈↓ ↓H␈↓product␈αis␈αdetermined␈αby␈αequality␈αof␈αthe␈αindices␈α  ␈↓αi␈↓␈α  and␈α  ␈↓αj␈↓␈α  rather␈α than␈αequality␈αof␈αthe␈αterms␈α ␈↓αe␈↓¬i␈↓
␈↓ ↓H␈↓and ␈↓αe␈↓¬j␈↓.

␈↓ ↓H␈↓        Two␈αmore␈αuseful␈αfunctions␈αwith␈αfunctions␈αas␈αarguments␈αare␈αthe␈αpredicates␈α ␈↓αandlis␈↓␈α and␈α ␈↓αorlis␈↓
␈↓ ↓H␈↓defined by the equations

␈↓ ↓H␈↓        ␈↓αandlis␈↓↓[␈↓αu, p␈↓↓] ← ␈↓βn ␈↓αu ␈↓↓∨ [␈↓αp␈↓↓[␈↓βa ␈↓αu␈↓↓] ∧ ␈↓αandlis␈↓↓[␈↓βd ␈↓αu, p␈↓↓]]
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :20


␈↓ ↓H␈↓↓␈↓and

␈↓ ↓H␈↓        ␈↓αorlis␈↓↓[␈↓αu, p␈↓↓] ← ¬␈↓βn ␈↓αu ␈↓↓∧ [␈↓αp␈↓↓[␈↓βa ␈↓αu␈↓↓] ∨ ␈↓αorlis␈↓↓[␈↓βd ␈↓αu, p␈↓↓]].

␈↓ ↓H␈↓↓␈↓        ␈↓↓The internal form for a λ-expression is

␈↓ ↓H␈↓↓␈↓        ␈↓↓␈↓∧(LAMBDA <list of variables> <expression to be evaluated>)␈↓.

␈↓ ↓H␈↓Thus␈α␈↓↓λ␈αx:␈α
diff[x,v]␈↓␈αis␈αwritten␈α␈↓∧(LAMBDA␈α
(X␈αV)␈α(DIFF␈α
X␈αV))␈↓.␈α When␈αa␈α
function␈αspecified␈αwith␈α
λ␈αis
␈↓ ↓H␈↓written␈α⊃as␈α⊃an␈α∩argument␈α⊃of␈α⊃a␈α∩function␈α⊃taking␈α⊃a␈α⊃functional␈α∩argument,␈α⊃then␈α⊃the␈α∩λ-expression␈α⊃is
␈↓ ↓H␈↓marked with the identifier ␈↓∧FUNCTION␈↓.  Thus the above definition of ␈↓αdiff␈↓ translates to
␈↓ ↓H␈↓        ␈↓∧(DE DIFF (E V) (COND
␈↓ ↓H␈↓∧␈↓                ␈↓∧((ATOM E) (COND ((EQ E V) 1) (T 0)))
␈↓ ↓H␈↓∧␈↓                ␈↓∧((EQ (CAR E) (QUOTE PLUS))

␈↓ ↓H␈↓∧                        (CONS␈α(QUOTE␈αPLUS)␈α(MAPCAR␈α(CDR␈αE)␈α(FUNCTION␈α(LAMBDA␈α(X)␈α(DIFF
␈↓ ↓H␈↓∧X V))))))

␈↓ ↓H␈↓∧␈↓                ␈↓∧((EQ␈α≥(CAR␈α≥E)␈α≥(QUOTE␈α≥TIMES))␈α≥                        (CONS␈α≥(QUOTE␈α≥PLUS)
␈↓ ↓H␈↓∧(MAPLIST␈α∪(CDR␈α∀E)␈α∪(FUNCTION␈α∪(LAMBDA␈α∀(X)␈α∪(CONS␈α∪(QUOTE␈α∀TIMES)␈α∪(MAPLIS␈α∀(CDR␈α∪E)
␈↓ ↓H␈↓∧(FUNCTION (LAMBDA (Y) (COND ((EQ X Y) (DIFF (CAR Y) V)) (T (CAR Y))))))))))))))␈↓.

␈↓ ↓H␈↓                              Exercises

␈↓ ↓H␈↓        1.␈α
Compute␈α ␈↓αdiff␈↓↓[␈↓∧(TIMES␈α
X␈α
(PLUS␈αY␈α
1)␈α3),␈α
X␈↓↓]␈↓␈α
 using␈α the␈α
 above␈α
definition␈α of␈α
 ␈↓αdiff␈↓.␈α Now␈α
do
␈↓ ↓H␈↓you see why algebraic simplification is important?

␈↓ ↓H␈↓        2. Compute  ␈↓αorlis␈↓↓[␈↓∧((A B) (C D) E), ␈↓βat␈↓↓]␈↓.



␈↓ ↓H␈↓10.  ␈↓βLabel.␈↓


␈↓ ↓H␈↓        The␈α
λ␈αmechanism␈α
is␈α
 not␈α adequate␈α
 for␈α
 providing␈α names␈α
 for␈α
recursive␈α functions,␈α
 because
␈↓ ↓H␈↓in␈α∪this␈α∪case␈α∩there␈α∪has␈α∪to␈α∩be␈α∪a␈α∪way␈α∪of␈α∩referring␈α∪to␈α∪the␈α∩function␈α∪name␈α∪within␈α∪the␈α∩ function.
␈↓ ↓H␈↓Therefore,␈α we␈αuse␈α the␈αnotation␈α ␈↓βlabel␈↓↓[␈↓αf,␈αe␈↓↓]␈↓␈α to␈αdenote␈αthe␈αexpression␈α ␈↓αe␈↓␈α but␈αwhere␈αoccurrences␈αof
␈↓ ↓H␈↓␈↓αf␈↓␈α⊃ within␈α⊃ ␈↓αe␈↓␈α⊃ refer␈α⊃ to␈α⊃ the␈α⊃ whole␈α∩ expression.␈α⊃ For␈α⊃example,␈α⊃ suppose␈α⊃we␈α⊃wished␈α⊃to␈α∩define␈α⊃a
␈↓ ↓H␈↓function␈αthat␈α
takes␈αalternate␈αelements␈α
of␈αeach␈α
element␈αof␈αa␈α
list␈αand␈α
makes␈αa␈αlist␈α
of␈αthese.␈α  Thus,␈α
we
␈↓ ↓H␈↓want

␈↓ ↓H␈↓        ␈↓αglub␈↓↓[␈↓∧((A B C) (A B C D) (X Y Z))␈↓↓] = ␈↓∧((A C) (A C) (X Z)).␈↓

␈↓ ↓H␈↓We can make the definition

␈↓ ↓H␈↓        ␈↓αglub␈↓↓[␈↓αx␈↓↓]␈α←␈α
␈↓αmapcar␈↓↓[␈↓αx,␈α␈↓βlabel␈↓↓[␈↓αalt␈↓↓,␈αλ␈↓αx␈↓↓:␈α
␈↓βif␈αn␈α
␈↓αx␈α␈↓↓∨␈α␈↓βn␈α
d␈α␈↓αx␈α
␈↓βthen␈α␈↓αx␈α                                        ␈↓βelse␈α
a
␈↓ ↓H␈↓β␈↓αx . alt␈↓↓[␈↓βdd ␈↓αx␈↓↓]]].
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :21


␈↓ ↓H␈↓↓␈↓        ␈↓↓The␈α∪internal␈α∪form␈α∪of␈α∪␈↓αlabel[<name>,<function␈α∪expression>]␈↓␈α∪is␈α∪␈↓∧(LABEL␈α∀<name>␈α∪<function
␈↓ ↓H␈↓∧expression>)␈↓, so that the internal form of the definition of ␈↓αglub␈↓ is

␈↓ ↓H␈↓        ␈↓∧(DE␈α⊃GLUB␈α⊂(X)␈α⊃(MAPCAR␈α⊂X␈α⊃(LABEL␈α⊂ALT␈α⊃(LAMBDA␈α⊂(X)␈α⊃(COND␈α⊂(OR␈α⊃(NULL␈α⊃X)␈α⊂(NULL
␈↓ ↓H␈↓∧(CDR X))) X) (T (CONS (CAR X) (ALT (CDDR X))))))))␈↓.

␈↓ ↓H␈↓        The␈α⊂identifier␈α⊂ ␈↓αalt␈↓␈α⊂ in␈α∂the␈α⊂above␈α⊂example␈α⊂is␈α∂bound␈α⊂by␈α⊂the␈α⊂ label␈α∂ and␈α⊂is␈α⊂ local␈α⊂ to␈α∂ that
␈↓ ↓H␈↓expression,␈α and␈α this␈α
is␈αthe␈αgeneral␈α
rule.␈α The␈αlabel␈α construction␈α
is␈αnot␈αoften␈α
used␈αin␈αLISP␈αsince␈α
it
␈↓ ↓H␈↓is␈α∂more␈α∂usual␈α∂to␈α∂ give␈α∞functions␈α∂global␈α∂definitions.␈α∂D.␈α∂M.␈α∂R.␈α∞Park␈α∂pointed␈α∂out␈α∂that␈α∂if␈α∂we␈α∞allow
␈↓ ↓H␈↓variables␈α∂to␈α∂represent␈α∂functions␈α∂and␈α∞use␈α∂a␈α∂ suitable␈α∂  λ␈α∂construction,␈α∞the␈α∂use␈α∂of␈α∂ label␈α∂ could␈α∞be
␈↓ ↓H␈↓avoided.
␈↓ ↓H␈↓␈↓ εP␈↓ :22


␈↓ ↓H␈↓β␈↓ ¬rCHAPTER II

␈↓ ↓H␈↓β␈↓ β.HOW TO WRITE RECURSIVE FUNCTION DEFINITIONS






␈↓ ↓H␈↓1.  ␈↓βStatic and dynamic ways of programming.␈↓


␈↓ ↓H␈↓        In␈α∪ order␈α∪ to␈α∀ write␈α∪recursive␈α∪function␈α∪definitions,␈α∀one␈α∪must␈α∪think␈α∀about␈α∪programming
␈↓ ↓H␈↓differently␈α
than␈αis␈α
 customary␈α when␈α
 writing␈α
programs␈α in␈α
 languages␈αlike␈α
Fortran␈αor␈α
Algol␈α
or␈αin
␈↓ ↓H␈↓machine␈α∀language.␈α∀ In␈α∀these␈α∃languages,␈α∀one␈α∀has␈α∀in␈α∀mind␈α∃the␈α∀state␈α∀of␈α∀the␈α∃ computation␈α∀ as
␈↓ ↓H␈↓represented␈α
 by␈α∞ the␈α
 values␈α∞of␈α
certain␈α∞variables␈α
or␈α∞locations␈α
in␈α∞the␈α
memory␈α∞of␈α
the␈α∞machine,␈α
and
␈↓ ↓H␈↓then␈α∂ one␈α∂ writes␈α∂ statements␈α∂ or␈α∂ machine␈α∂instructions␈α∞in␈α∂order␈α∂to␈α∂make␈α∂the␈α∂state␈α∂change␈α∂in␈α∞an
␈↓ ↓H␈↓appropriate way.

␈↓ ↓H␈↓        When␈αwriting␈α
LISP␈αrecursive␈α
functions␈αone␈α
thinks␈αdifferently.␈α
 Namely,␈αone␈α
thinks␈αabout␈α
the
␈↓ ↓H␈↓value␈α⊂of␈α⊂the␈α⊃ function,␈α⊂ asks␈α⊂ for␈α⊂ what␈α⊃values␈α⊂ of␈α⊂the␈α⊂arguments␈α⊃the␈α⊂value␈α⊂of␈α⊂the␈α⊃function␈α⊂is
␈↓ ↓H␈↓immediate,␈α∂and,␈α∂given␈α∂ an␈α∂ arbitrary␈α∂ values␈α∂ of␈α∂ the␈α∂ arguments,␈α∂ for␈α∂ what␈α∂ simpler␈α∂arguments
␈↓ ↓H␈↓must␈α
 the␈α function␈α
be␈αknown␈α
in␈αorder␈α
to␈αgive␈α
the␈αvalue␈α
of␈αthe␈α
function␈αfor␈α
 the␈α given␈α
 arguments.
␈↓ ↓H␈↓Let␈α us␈α take␈α a␈α numerical␈αexample;␈α namely,␈α suppose␈α we␈αwant␈αto␈αcompute␈αthe␈αfunction␈α ␈↓αn␈↓↓!␈↓.␈α For
␈↓ ↓H␈↓what␈αargument␈αis␈αthe␈αvalue␈αof␈αthe␈αfunction␈αimmediate.␈α  Clearly,␈α for␈α␈↓αn␈α␈↓↓=␈α␈↓∧0␈α or␈α ␈↓αn␈α␈↓↓=␈α␈↓∧1␈↓,␈αthe␈αvalue␈αis
␈↓ ↓H␈↓immediately␈α
seen␈α∞to␈α
be␈α
 1.␈α∞ Moreover,␈α
we␈α
can␈α∞get␈α
the␈α
value␈α∞for␈α
an␈α
arbitrary␈α∞ ␈↓αn␈↓␈α
 if␈α
we␈α∞know␈α
 the
␈↓ ↓H␈↓value␈α∞ for␈α∞␈↓αn␈↓↓-␈↓∧1.␈α∞  Also,␈α∂we␈α∞see␈α∞that␈α∞knowing␈α∞the␈α∂value␈α∞for␈α∞ ␈↓αn␈α∞␈↓↓=␈α∞␈↓∧1␈α∂ is␈α∞redundant,␈α∞since␈α∞it␈α∂can␈α∞be
␈↓ ↓H␈↓∧obtained␈αfrom␈αthe␈α ␈↓αn␈α
␈↓↓=␈α␈↓∧0␈α case␈αby␈αthe␈α
 same␈α rule␈α as␈αgets␈α it␈α
 for␈α a␈α general␈α ␈↓αn␈↓∧␈α from␈α
the␈αvalue
␈↓ ↓H␈↓∧for  ␈↓αn␈↓↓-␈↓∧1␈↓.  All this talk leads to the simple recursive formula:

␈↓ ↓H␈↓        ␈↓αn␈↓↓! ← ␈↓βif ␈↓αn ␈↓↓= ␈↓∧0 ␈↓βthen ␈↓∧1 ␈↓βelse ␈↓αn␈↓↓(␈↓αn␈↓↓-␈↓∧1␈↓↓)!.

␈↓ ↓H␈↓↓␈↓        ␈↓↓␈↓We␈αmay␈αregard␈αthis␈αas␈αa␈αstatic␈αway␈αof␈αlooking␈αat␈αprogramming.␈α We␈αask␈αwhat␈αsimpler␈αcases
␈↓ ↓H␈↓the␈α
general␈αcase␈α
of␈α
our␈αfunction␈α
depends␈α
on␈αrather␈α
 than␈α
 how␈α we␈α
 build␈α
up␈αthe␈α
desired␈α
state␈αof
␈↓ ↓H␈↓the␈αcomputation.␈α
 One␈αoften␈α
is␈αled␈α
to␈αbelieve␈αthat␈α
 static␈α=␈α
bad␈α and␈α
  dynamic␈α=␈α
good,␈αbut␈α in␈α
 this
␈↓ ↓H␈↓case,␈α the␈αstatic␈αway␈αis␈αoften␈αbetter␈αthan␈αthe␈αdynamic␈αway.␈α Perhaps␈αthis␈αdistinction␈αis␈αequivalent␈αto
␈↓ ↓H␈↓what␈α∞some␈α∞people␈α∞call␈α
the␈α∞distinction␈α∞between␈α∞␈↓αtop-down␈↓␈α
and␈α∞␈↓αbottom-up␈↓␈α∞programming␈α∞with␈α
␈↓αstatic␈↓
␈↓ ↓H␈↓corresponding␈αto␈α␈↓αtop-down␈↓.␈α LISP␈αoffers␈αboth,␈αbut␈αthe␈αstatic␈αstyle␈αis␈αbetter␈αdeveloped␈αin␈αLISP,␈αand
␈↓ ↓H␈↓we will emphasize it.

␈↓ ↓H␈↓        Compare␈α∂ the␈α∂ above␈α∂ recursive␈α∂ definition␈α∂with␈α∂the␈α∂following␈α∂obvious␈α∂Algol␈α∂program␈α∞for
␈↓ ↓H␈↓computing  ␈↓αn␈↓↓!:

␈↓ ↓H␈↓↓␈↓        ␈↓↓␈↓βinteger procedure ␈↓αfactorial␈↓↓(␈↓αn␈↓↓); ␈↓βinteger ␈↓αs␈↓↓;
␈↓ ↓H␈↓↓␈↓βbegin
␈↓ ↓H␈↓β␈↓        ␈↓β␈↓αs ␈↓↓:= ␈↓∧1␈↓↓;
␈↓ ↓H␈↓↓␈↓αloop␈↓↓:       ␈↓βif ␈↓αn ␈↓↓= ␈↓∧0 ␈↓βthen go to ␈↓αdone␈↓↓;
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :23


␈↓ ↓H␈↓↓␈↓        ␈↓↓␈↓αs ␈↓↓:= ␈↓αn␈↓↓*␈↓αs␈↓↓;
␈↓ ↓H␈↓↓␈↓        ␈↓↓␈↓αn ␈↓↓:= ␈↓αn␈↓↓-␈↓∧1␈↓↓;
␈↓ ↓H␈↓↓␈↓        ␈↓↓␈↓βgo to ␈↓αloop␈↓↓;
␈↓ ↓H␈↓↓␈↓αdone␈↓↓:       ␈↓αfactorial ␈↓↓:= ␈↓αs␈↓↓;
␈↓ ↓H␈↓↓␈↓βend␈↓↓;

␈↓ ↓H␈↓↓␈↓        ␈↓↓␈↓The␈α⊂ LISP␈α∂program␈α⊂is␈α∂shorter␈α⊂and␈α∂clearer␈α⊂in␈α∂this␈α⊂particularly␈α∂favorable␈α⊂ case.␈α∂  Actually,
␈↓ ↓H␈↓when␈α we␈α discuss␈α
 the␈α  mechanism␈α  of␈α
recursion,␈αit␈αwill␈α
turn␈αout␈αthat␈α
the␈αLISP␈αprogram␈α
will␈αbe
␈↓ ↓H␈↓inefficient␈α∪in␈α∩using␈α∪the␈α∩pushdown␈α∪mechanism␈α∪unnecessarily␈α∩and␈α∪should␈α∩be␈α∪ replaced␈α∪by␈α∩ the
␈↓ ↓H␈↓following␈α∃ somewhat␈α∃ longer␈α∀ program␈α∃that␈α∃corresponds␈α∃to␈α∀the␈α∃above␈α∃Algol␈α∃program␈α∀rather
␈↓ ↓H␈↓precisely:

␈↓ ↓H␈↓        ␈↓αn␈↓↓! ← ␈↓αfact␈↓↓(␈↓αn␈↓↓, ␈↓αs␈↓↓),

␈↓ ↓H␈↓↓␈↓where

␈↓ ↓H␈↓        ␈↓αfact␈↓↓(␈↓αn␈↓↓, ␈↓αs␈↓↓) ← ␈↓βif ␈↓αn ␈↓↓= ␈↓∧0 ␈↓βthen ␈↓αs ␈↓βelse ␈↓αfact␈↓↓(␈↓αn␈↓↓-␈↓∧1␈↓↓, ␈↓αn␈↓↓*␈↓αs␈↓↓).

␈↓ ↓H␈↓↓␈↓In  fact,  compilers should produce the same object code from the two programs.



␈↓ ↓H␈↓2.  ␈↓βSimple list recursion.␈↓


␈↓ ↓H␈↓        About␈α
the␈α
simplest␈α
form␈α
of␈α
recursion␈α
in␈α
LISP␈αoccurs␈α
when␈α
 one␈α
of␈α
the␈α
arguments␈α
is␈α
a␈αlist,␈α
the
␈↓ ↓H␈↓result␈αis␈αimmediate␈αwhen␈αthe␈αargument␈αis␈αnull,␈αand␈αotherwise␈αwe␈αneed␈αonly␈αknow␈αthe␈αresult␈αfor␈αthe
␈↓ ↓H␈↓␈↓βd␈↓-part␈α∂of␈α∂that␈α∂argument.␈α∂ Consider,␈α∂for␈α∂example,␈α∞ ␈↓αu␈↓↓*␈↓αv␈↓,␈α∂the␈α∂concatenation␈α∂of␈α∂the␈α∂lists␈α∂ ␈↓αu␈↓␈α∂ and␈α∞␈↓αv␈↓.
␈↓ ↓H␈↓The␈αresult␈αis␈αimmediate␈αfor␈α the␈α case␈α  ␈↓βn␈α␈↓αu␈↓␈α  and␈αotherwise␈αdepends␈αon␈αthe␈αresult␈αfor␈α ␈↓βd␈α␈↓αu␈↓.␈α Thus,
␈↓ ↓H␈↓we have

␈↓ ↓H␈↓        ␈↓αu␈↓↓*␈↓αv ␈↓↓← ␈↓βif n ␈↓αu ␈↓βthen ␈↓αv ␈↓βelse a ␈↓αu ␈↓↓. [␈↓βd ␈↓αu ␈↓↓* ␈↓αv␈↓↓].

␈↓ ↓H␈↓↓␈↓On␈α∞the␈α∞other␈α∞hand,␈α∞if␈α∞we␈α∞had␈α∞tried␈α∞to␈α∞recur␈α∞on␈α∞ ␈↓αv␈↓␈α∞ rather␈α∞than␈α∞on␈α∞ ␈↓αu␈↓␈α∞we␈α∞would␈α∞not␈α∞have␈α∞been
␈↓ ↓H␈↓successful.␈α The␈α
result␈αwould␈α
be␈αimmediate␈α
for␈α␈↓βn␈α␈↓αv␈↓,␈α
but␈α ␈↓αu␈↓↓*␈↓αv␈↓␈α
 cannot␈αbe␈α
constructed␈αin␈α
any␈αdirect
␈↓ ↓H␈↓way␈α∞from␈α∞  ␈↓αu␈↓↓*␈↓βd␈α∞␈↓αv␈↓␈α∞without␈α∞ a␈α∞ function␈α∞ that␈α∞ puts␈α∞ an␈α∞ element␈α∞onto␈α∞the␈α∞end␈α∞of␈α∞a␈α∞list.␈α∂ (From␈α∞a
␈↓ ↓H␈↓strictly␈α∂list␈α∂point␈α∂of␈α∂view,␈α∂such␈α∂ a␈α⊂ function␈α∂ would␈α∂ be␈α∂ as␈α∂elementary␈α∂ as␈α∂ ␈↓αcons␈↓␈α∂ which␈α⊂puts␈α∂an
␈↓ ↓H␈↓element␈αonto␈αthe␈αfront␈αof␈αa␈αlist,␈αbut,␈αwhen␈αwe␈αconsider␈αthe␈αimplementation␈αof␈αlists␈αby␈αlist␈αstructures,
␈↓ ↓H␈↓we␈α see␈α that␈α the␈α function␈αis␈αnot␈αso␈αelementary.␈α This␈αhas␈αled␈αsome␈αpeople␈αto␈αconstruct␈αsystems␈αin
␈↓ ↓H␈↓which␈αlists␈αare␈α bi-directional,␈α but,␈αin␈α the␈α main,␈α this␈αhas␈αturned␈αout␈αto␈αbe␈αa␈αbad␈αidea).␈α Anyway,
␈↓ ↓H␈↓it is usually easier to recur on one argument of a function than  to  recur on the other.

␈↓ ↓H␈↓        It␈α∞ is␈α
 often␈α∞necessary␈α∞to␈α
represent␈α∞a␈α
correspondence␈α∞between␈α∞the␈α
elements␈α∞of␈α
a␈α∞small␈α∞set␈α
of
␈↓ ↓H␈↓atoms␈α
and␈α
certain␈α
 S-expressions␈α
 by␈α
 a␈α
list␈α
structure.␈α
 This␈α
is␈α
conveniently␈α
done␈α
by␈α
means␈α
of␈α
an
␈↓ ↓H␈↓association␈αlist␈αwhich␈αis␈αa␈αlist␈αof␈αpairs,␈αeach␈αpair␈αconsisting␈αof␈α an␈α atom␈α and␈αthe␈αcorresponding␈α
S-
␈↓ ↓H␈↓expression. Thus the association list
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :24


␈↓ ↓H␈↓        ␈↓∧((X . (PLUS A B)) (Y . C) (Z . (TIMES U V)),

␈↓ ↓H␈↓∧␈↓which would print as

␈↓ ↓H␈↓        ␈↓∧((X PLUS A B)) (Y . C) (Z TIMES U V)),

␈↓ ↓H␈↓∧␈↓pairs␈α
 ␈↓∧X␈↓␈α∞ with␈α
 ␈↓∧(PLUS␈α
A␈α∞B),␈α
 Y␈↓␈α∞ with␈α
 ␈↓∧C␈↓,␈α
etc.␈α∞We␈α
need␈α∞a␈α
 function␈α
 to␈α∞tell␈α
 whether␈α∞ anything␈α
 is
␈↓ ↓H␈↓associated  with  the  atom   ␈↓αx␈↓   in the association list  ␈↓αa␈↓, and, if so, to tell us what. We have

␈↓ ↓H␈↓        ␈↓αassoc␈↓↓[␈↓αx, a␈↓↓] ← ␈↓βif n ␈↓αa ␈↓βthen ␈↓∧NIL ␈↓βelse if ␈↓αx ␈↓βeq aa ␈↓αa ␈↓βthen a ␈↓αa
␈↓ ↓H␈↓α␈↓                ␈↓α␈↓βelse ␈↓αassoc␈↓↓[␈↓αx, ␈↓βd ␈↓αa␈↓↓].

␈↓ ↓H␈↓↓␈↓Its␈α
value␈α
is␈α
  ␈↓∧NIL␈↓␈α
  if␈α
 nothing␈α
 is␈α
 associated␈α
 with␈α
  ␈↓αx␈↓␈α
  and␈α
 the␈α
association␈α
pair␈α∞otherwise.␈α
 E.g.
␈↓ ↓H␈↓␈↓αassoc␈↓↓[␈↓∧X, ((X.W) (Y.V))␈↓↓] = ␈↓∧(X.W)␈↓.

␈↓ ↓H␈↓        It␈α
 commonly␈α
happens␈α
that␈α
a␈α
function␈α
has␈α
no␈α
simple␈α
recursion,␈α
but␈α
there␈α
is␈α
a␈αsimple␈α
recursion
␈↓ ↓H␈↓for␈α⊃a␈α∩function␈α⊃with␈α⊃one␈α∩more␈α⊃variable␈α⊃that␈α∩ reduces␈α⊃ to␈α⊃the␈α∩desired␈α⊃function␈α⊃when␈α∩the␈α⊃extra
␈↓ ↓H␈↓variable is set to ␈↓∧NIL␈↓.  Thus

␈↓ ↓H␈↓        ␈↓αreverse␈↓↓[␈↓αu␈↓↓] ← ␈↓αrev1␈↓↓[␈↓αx, ␈↓∧NIL␈↓↓],

␈↓ ↓H␈↓↓␈↓where

␈↓ ↓H␈↓        ␈↓αrev1␈↓↓[␈↓αu, v␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓αv ␈↓βelse ␈↓αrev1␈↓↓[␈↓βd ␈↓αu, ␈↓βa ␈↓αu . v␈↓↓].

␈↓ ↓H␈↓↓␈↓αreverse␈↓␈α
has␈αa␈α
direct␈αrecursive␈α
definition␈α
as␈αdiscovered␈α
by␈αS.␈α
Ness,␈α
but␈αno-one␈α
would␈αwant␈α
to␈αuse␈α
the
␈↓ ↓H␈↓following␈α∞in␈α∞actual␈α∞computation␈α∞ nor␈α∞does␈α∞ it␈α∞generate␈α∞much␈α∞understanding,␈α∞only␈α∞appreciation␈α∞of
␈↓ ↓H␈↓Mr. Ness's ingenuity:

␈↓ ↓H␈↓        ␈↓αreverse␈↓↓[␈↓αu␈↓↓] ← ␈↓βif n ␈↓αu ␈↓↓∨ ␈↓βn d ␈↓αu ␈↓βthen ␈↓αu ␈↓βelse
␈↓ ↓H␈↓β␈↓                ␈↓βa ␈↓αreverse␈↓↓[␈↓βd ␈↓αu␈↓↓] . ␈↓αreverse␈↓↓[␈↓βa ␈↓αu. reverse␈↓↓[␈↓βd ␈↓αreverse␈↓↓[␈↓βd ␈↓αu␈↓↓]]].



␈↓ ↓H␈↓                              Exercises

␈↓ ↓H␈↓        1.␈αUsing␈α
the␈αfunction␈α ␈↓αmember␈↓↓[␈↓αx,␈α
u␈↓↓]␈↓␈α defined␈αin␈α
Chapter␈αI␈αwhich␈α
 may␈αalso␈αbe␈α
written␈α ␈↓αx␈α␈↓↓ε␈α
␈↓αu␈↓,
␈↓ ↓H␈↓write␈αfunction␈αdefinitions␈αfor␈αthe␈αunion␈α ␈↓αu␈α␈↓↓∪␈α␈↓αv␈↓␈α of␈αlists␈α ␈↓αu␈↓␈α and␈α ␈↓αv␈↓,␈αthe␈αintersection␈α ␈↓αu␈α␈↓↓∩␈α␈↓αv␈↓,␈α and␈α the
␈↓ ↓H␈↓set  difference   ␈↓αu␈↓↓-␈↓αv␈↓.    What  is  wanted  should  be clear from the examples:

␈↓ ↓H␈↓        ␈↓∧(A B C) ␈↓↓∪␈↓∧ (B C D) ␈↓↓=␈↓∧ (A B C D),

␈↓ ↓H␈↓∧␈↓        ␈↓∧(A B C) ␈↓↓∩␈↓∧ (B C D) ␈↓↓=␈↓∧ (B C),

␈↓ ↓H␈↓∧␈↓and

␈↓ ↓H␈↓        ␈↓∧(A B C) ␈↓↓-␈↓∧ (B C D) ␈↓↓=␈↓∧ (A).
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :25


␈↓ ↓H␈↓∧␈↓Pay␈α∂ attention␈α∂ to␈α∂getting␈α∂correct␈α∂the␈α∂trivial␈α∂cases␈α∂in␈α∂which␈α∂some␈α∂of␈α∂the␈α∂arguments␈α∂are␈α⊂␈↓∧NIL␈↓.␈α∂ In
␈↓ ↓H␈↓general, it  is  important  to  understand clearly the trivial cases of functions.

␈↓ ↓H␈↓        2.␈α⊂ Suppose␈α⊂  ␈↓αx␈↓␈α⊂  takes␈α⊃ numbers␈α⊂ as␈α⊂ values␈α⊂and␈α⊂ ␈↓αu␈↓␈α⊃ takes␈α⊂as␈α⊂values␈α⊂lists␈α⊂of␈α⊃numbers␈α⊂in
␈↓ ↓H␈↓ascending␈α∞order,␈α∞e.g.␈α∞ ␈↓∧(2␈α∞4␈α∞7)␈↓.␈α∞  Write␈α
 a␈α∞function␈α∞  ␈↓αmerge␈↓↓[␈↓αx,␈α∞u␈↓↓]␈↓␈α∞  whose␈α∞ value␈α∞ is␈α∞obtained␈α
from
␈↓ ↓H␈↓that␈αof␈α ␈↓αu␈↓␈α by␈αputting␈α    ␈↓αx␈↓␈α    in␈α    ␈↓αu␈↓␈α    in␈α   its␈α   proper␈α   place.␈α    Thus␈α␈↓αmerge␈↓↓[␈↓∧3,␈α(2␈α4)␈↓↓]␈α=␈α␈↓∧(2␈α3
␈↓ ↓H␈↓∧4)␈↓, and  ␈↓αmerge␈↓↓[␈↓∧3, (2 3)␈↓↓] = ␈↓∧(2 3 3)␈↓.

␈↓ ↓H␈↓        3.␈α∂ Write␈α∞ functions␈α∂ giving␈α∞the␈α∂union,␈α∞intersection,␈α∂and␈α∞set␈α∂difference␈α∞of␈α∂ordered␈α∂lists;␈α∞the
␈↓ ↓H␈↓result is wanted as an ordered list.

␈↓ ↓H␈↓        Note␈α⊂that␈α∂computing␈α⊂these␈α∂functions␈α⊂of␈α⊂unordered␈α∂lists␈α⊂ takes␈α∂a␈α⊂ number␈α⊂ of␈α∂comparisons
␈↓ ↓H␈↓proportional␈αto␈αthe␈αsquare␈α
of␈αthe␈αnumber␈αof␈α
elements␈αof␈αa␈αtypical␈α
list,␈αwhile␈αfor␈αordered␈α
lists,␈α the
␈↓ ↓H␈↓number  of comparisons is proportional to the number of elements.

␈↓ ↓H␈↓        4.␈α
 Using␈α
  ␈↓αmerge␈↓,␈α∞write␈α
a␈α
function␈α∞ ␈↓αsort␈↓␈α
 that␈α
transforms␈α
an␈α∞unordered␈α
list␈α
into␈α∞an␈α
ordered
␈↓ ↓H␈↓list.

␈↓ ↓H␈↓        5.␈α∃Write␈α⊗a␈α∃function␈α∃ ␈↓αgoodsort␈↓␈α⊗ that␈α∃ sorts␈α⊗ a␈α∃ list␈α∃ using␈α⊗ a␈α∃number␈α⊗ of␈α∃ comparisons
␈↓ ↓H␈↓proportional  to   ␈↓αn log n␈↓, where  ␈↓αn␈↓  is the length of the list to be sorted.



␈↓ ↓H␈↓3.  ␈↓βSimple S-expression recursion.␈↓


␈↓ ↓H␈↓        In␈αanother␈αclass␈αof␈αproblems,␈αthe␈αvalue␈αof␈α the␈α function␈α is␈αimmediate␈α for␈α
 atomic␈αsymbols,
␈↓ ↓H␈↓and␈α∞for␈α∞non␈α∞atoms␈α∞depends␈α∞only␈α∞on␈α∞the␈α∞values␈α∞for␈α∞ the␈α∞a-part␈α∞and␈α∞the␈α∞d-part␈α∞of␈α∞the␈α
argument.
␈↓ ↓H␈↓Thus   ␈↓αsubst␈↓ was defined by

␈↓ ↓H␈↓        ␈↓αsubst␈↓↓[␈↓αx, y, z␈↓↓] ← ␈↓βif at ␈↓αz ␈↓βthen ␈↓↓[␈↓βif ␈↓αz ␈↓βeq ␈↓αy ␈↓βthen ␈↓αx ␈↓βelse ␈↓αz␈↓↓]
␈↓ ↓H␈↓↓                        ␈↓βelse ␈↓αsubst␈↓↓[␈↓αx, y, ␈↓βa ␈↓αz␈↓↓] . ␈↓αsubst␈↓↓[␈↓αx , y , ␈↓βd ␈↓αz␈↓↓].

␈↓ ↓H␈↓↓␈↓        ␈↓↓␈↓Two␈α⊃other␈α⊃examples␈α⊃are␈α⊃ ␈↓αequal␈↓␈α⊃ which␈α⊃gives␈α⊃ the␈α⊃ equality␈α⊃ of␈α⊃S-expressions␈α⊃ and␈α⊂  ␈↓αflat␈↓
␈↓ ↓H␈↓which spreads an S-expression into a list of atoms:  They are defined by

␈↓ ↓H␈↓        ␈↓αx␈↓↓=␈↓αy ␈↓↓← ␈↓αx ␈↓βeq ␈↓αy ␈↓↓∨ [¬␈↓βat ␈↓αx ␈↓↓∧ ¬␈↓βat ␈↓αy ␈↓↓∧ ␈↓βa ␈↓αx ␈↓↓= ␈↓βa ␈↓αy ␈↓↓∧ ␈↓βd ␈↓αx ␈↓↓= ␈↓βd ␈↓αy␈↓↓],

␈↓ ↓H␈↓↓␈↓and

␈↓ ↓H␈↓        ␈↓αflat␈↓↓[␈↓αx␈↓↓] ← ␈↓αflata␈↓↓[␈↓αx, ␈↓∧NIL␈↓↓]

␈↓ ↓H␈↓↓␈↓where

␈↓ ↓H␈↓        ␈↓αflata␈↓↓[␈↓αx, u␈↓↓] ← ␈↓βif at ␈↓αx ␈↓βthen ␈↓αx.y ␈↓βelse ␈↓αflata␈↓↓[␈↓βa ␈↓αx, flata␈↓↓[␈↓βd ␈↓αx, y␈↓↓]].

␈↓ ↓H␈↓↓␈↓                              EXERCISES
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :26


␈↓ ↓H␈↓        1.␈α
Write␈α
a␈αpredicate␈α
to␈α
tell␈αwhether␈α
a␈α
given␈αatom␈α
occurs␈α
in␈αa␈α
given␈α
S-expression,␈αe.g.␈α
 ␈↓αoccur␈↓↓[␈↓∧B,
␈↓ ↓H␈↓∧((A.B).C)␈↓↓] = ␈↓∧T␈↓.

␈↓ ↓H␈↓        2. Write a predicate to tell how  many  times  a  given  atom occurs in an S-expression.

␈↓ ↓H␈↓        3.␈α∞ Write␈α∞ a␈α∞ function␈α∞to␈α
make␈α∞a␈α∞list␈α∞without␈α∞duplications␈α
of␈α∞the␈α∞atoms␈α∞occurring␈α∞in␈α∞an␈α
S-
␈↓ ↓H␈↓expression.

␈↓ ↓H␈↓        4.␈αWrite␈αa␈α
function␈αto␈αmake␈αa␈α
list␈αof␈αall␈α
 atoms␈α that␈α occur␈αmore␈α
  than␈α  once␈α  in␈α  a␈α
 given
␈↓ ↓H␈↓S-expression  paired  with  their multiplicities.

␈↓ ↓H␈↓        5.␈α
Write␈αa␈α
predicate␈α
to␈αtell␈α
whether␈αan␈α
S-expression␈α
has␈αmore␈α
than␈α
one␈αoccurrence␈α
of␈αa␈α
given
␈↓ ↓H␈↓S-expression as a sub-expression.



␈↓ ↓H␈↓4.  ␈↓βOther structural recursions.␈↓


␈↓ ↓H␈↓        When␈α↔lists␈α_are␈α↔used␈α_to␈α↔represent␈α_algebraic␈α↔expressions,␈α_functions␈α↔of␈α_these␈α↔algebraic
␈↓ ↓H␈↓expressions␈α⊗often␈α⊗have␈α⊗a␈α⊗recursive␈α⊗form␈α⊗closely␈α⊗related␈α⊗to␈α⊗the␈α⊗inductive␈α⊗definition␈α⊗of␈α∃the
␈↓ ↓H␈↓expressions.␈α⊂ Suppose,␈α⊂for␈α⊂example,␈α⊂that␈α⊂sums␈α⊂and␈α⊂products␈α⊂are␈α⊂represented␈α⊂respectively␈α⊂by␈α∂the
␈↓ ↓H␈↓forms␈α
 ␈↓∧(PLUS␈α
X␈αY)␈↓␈α
 and␈α
 ␈↓∧(TIMES␈α
X␈αY)␈↓␈α
 and␈α
that␈α
the␈αvalues␈α
of␈α
variables␈α
are␈αgiven␈α
on␈α
an␈αa-list.␈α
 We
␈↓ ↓H␈↓can write a recursive formula for the value of an expression as follows:

␈↓ ↓H␈↓        ␈↓αvalue␈↓↓[␈↓αe, a␈↓↓] ← ␈↓βif at ␈↓αe ␈↓βthen d ␈↓αassoc␈↓↓[␈↓αe, a␈↓↓]
␈↓ ↓H␈↓↓␈↓                ␈↓↓␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧PLUS ␈↓βthen ␈↓αvalue␈↓↓[␈↓βad ␈↓αe, a␈↓↓] + ␈↓αvalue␈↓↓[␈↓βadd ␈↓αe, a␈↓↓]
␈↓ ↓H␈↓↓␈↓                ␈↓↓␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧TIMES ␈↓βthen ␈↓αvalue␈↓↓[␈↓βad ␈↓αe, a␈↓↓] * ␈↓αvalue␈↓↓[␈↓βadd ␈↓αe, a␈↓↓].

␈↓ ↓H␈↓↓␈↓On␈αthe␈αother␈αhand,␈αsuppose␈αthat␈αsums␈αand␈αproducts␈αare␈αnot␈αrestricted␈αto␈αhave␈αjust␈αtwo␈αarguments;
␈↓ ↓H␈↓then we must use auxiliary functions to define the value of an expression, as follows:

␈↓ ↓H␈↓        ␈↓αvalue␈↓↓[␈↓αe, a␈↓↓] ← ␈↓βif at ␈↓αe ␈↓βthen d ␈↓αassoc␈↓↓[␈↓αe, a␈↓↓]
␈↓ ↓H␈↓↓                        ␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧PLUS ␈↓βthen ␈↓αvplus␈↓↓[␈↓βd ␈↓αe, a␈↓↓]
␈↓ ↓H␈↓↓                        ␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧TIMES ␈↓βthen ␈↓αvtimes␈↓↓[␈↓βd ␈↓αe, a␈↓↓].

␈↓ ↓H␈↓↓␈↓where

␈↓ ↓H␈↓        ␈↓αvplus␈↓↓[␈↓αu, a␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓∧0 ␈↓βelse ␈↓αvalue␈↓↓[␈↓βa ␈↓αu, a␈↓↓] + ␈↓αvplus␈↓↓[␈↓βd ␈↓αu, a␈↓↓],

␈↓ ↓H␈↓↓␈↓and

␈↓ ↓H␈↓        ␈↓αvtimes␈↓↓[␈↓αu, a␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓∧1 ␈↓βelse ␈↓αvalue␈↓↓[␈↓βa ␈↓αu, a␈↓↓] * ␈↓αvtimes␈↓↓[␈↓βd ␈↓αu, a␈↓↓].

␈↓ ↓H␈↓↓␈↓In␈α
both␈α
cases,␈αthe␈α
recursion␈α
form␈αis␈α
related␈α
to␈αthe␈α
structure␈α
of␈αthe␈α
algebraic␈α
expressions␈αmore␈α
closely
␈↓ ↓H␈↓than to the structure of S-expressions or lists.
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :27


␈↓ ↓H␈↓5.  ␈↓βTree search.␈↓


␈↓ ↓H␈↓        We␈α
begin␈α
with␈α
a␈α
general␈α
depth␈α
first␈α
tree␈α
search␈α
function.␈α
 It␈α
can␈α
be␈α
used␈α
to␈α
search␈α
specific
␈↓ ↓H␈↓trees␈αof␈α
possibilities␈αby␈α
defining␈αthree␈α
auxiliary␈αfunctions␈α
in␈αa␈α
way␈αthat␈α
depends␈αon␈αthe␈α
application.
␈↓ ↓H␈↓We have

␈↓ ↓H␈↓        ␈↓αsearch p ␈↓↓← ␈↓βif ␈↓αlose p ␈↓βthen ␈↓LOSE
␈↓ ↓H␈↓                         ␈↓βelse if ␈↓αter p ␈↓βthen ␈↓αp ␈↓βelse ␈↓αsearchlis␈↓↓[␈↓αsuccessors p␈↓↓]␈↓

␈↓ ↓H␈↓where


␈↓ ↓H␈↓        ␈↓αsearchlis␈αu␈α␈↓↓←␈α␈↓β␈αif␈αn␈α␈↓αu␈α␈↓βthen␈α␈↓LOSE␈α␈↓βelse␈α␈↓α␈↓↓{␈↓αsearch␈α␈↓βa␈α ␈↓αu␈↓↓}[␈↓αλx␈↓↓:␈↓α␈α␈↓βif␈α␈↓αx␈α␈↓↓=␈α␈↓LOSE␈α␈↓βthen␈α␈↓αsearchlis␈α␈↓βd␈α␈↓αu␈α␈↓βelse
␈↓ ↓H␈↓β␈↓αx␈↓↓]␈↓α.␈↓

␈↓ ↓H␈↓In␈α
the␈α
applications,␈α
we␈α
 start␈α
with␈α
a␈α
position␈α
␈↓αp␈↓¬0␈↓,␈α and␈α
we␈α
are␈α
looking␈α
for␈α
 a␈α
win␈α
in␈α
the␈αsuccessor␈α
tree
␈↓ ↓H␈↓of␈α␈↓αp␈↓¬0␈↓.␈α Certain␈αpositions␈αlose␈αand␈α there␈αis␈α no␈αpoint␈αlooking␈α at␈αtheir␈α successors.␈α This␈α
is␈αdecided
␈↓ ↓H␈↓by␈α
the␈α
predicate␈α
␈↓αlose␈↓.␈α
A␈α
position␈α
 is␈α
a␈α
win␈α
if␈α
it␈α
 doesn't␈α
 lose␈α
 and␈α
 it␈α
 satisfies␈α
 the␈α
 predicate␈α␈↓αter␈↓.
␈↓ ↓H␈↓The␈αsuccessors␈αof␈αa␈αposition␈α is␈αgiven␈αby␈αthe␈α function␈α␈↓αsuccessors␈↓,␈αand␈α the␈α value␈α of␈α␈↓αsearch␈α
 p␈↓␈α is
␈↓ ↓H␈↓the␈α∂ winning␈α∂position.␈α⊂   No␈α∂non-losing␈α∂position␈α⊂should␈α∂have␈α∂the␈α⊂ name␈α∂LOSE␈α∂or␈α⊂the␈α∂function
␈↓ ↓H␈↓won't work properly.

␈↓ ↓H␈↓        Our␈α⊂first␈α⊂example␈α⊂is␈α⊂ finding␈α⊂a␈α⊂path␈α⊂from␈α⊂an␈α⊂ initial␈α⊂node␈α⊂to␈α⊂a␈α⊂final␈α⊂node␈α⊂ in␈α⊂a␈α⊂graph
␈↓ ↓H␈↓represented␈α
by␈α
a␈α
list␈α
structure␈α
as␈α
described␈α
in␈αchapter␈α
I.␈α
  A␈α
position␈α
is␈α
a␈α
path␈α
 starting␈α
from␈αthe
␈↓ ↓H␈↓initial␈α
 node␈αand␈α
 continuing␈α
to␈α some␈α
intermediate␈α node␈α
and␈α
 is␈αrepresented␈α
 by␈α
a␈αlist␈α
 of␈αits␈α
nodes
␈↓ ↓H␈↓in reverse order.   The three  functions for this application are

␈↓ ↓H␈↓        ␈↓αlose p ␈↓↓← ␈↓βa ␈↓αp ␈↓↓ε ␈↓βd ␈↓αp,

␈↓ ↓H␈↓α␈↓        ␈↓αter p ␈↓↓← [␈↓βa ␈↓αp ␈↓↓=␈↓α final␈↓↓]␈↓α, ␈↓

␈↓ ↓H␈↓and

␈↓ ↓H␈↓        ␈↓αsuccessors p ␈↓↓←␈↓α mapcar␈↓↓[␈↓βd ␈↓αassoc␈↓↓[␈↓βa ␈↓αp, graph␈↓↓]␈↓α, λx␈↓↓:␈↓α x.p␈↓↓]␈↓α.␈↓

␈↓ ↓H␈↓        Another␈α
example␈αis␈α
the␈α
so-called␈α␈↓αInstant␈α
Insanity␈↓␈αpuzzle.␈α
 There␈α
are␈αfour␈α
cubical␈αblocks,␈α
and
␈↓ ↓H␈↓each␈αface␈αof␈α
each␈αblock␈αis␈α
colored␈αwith␈αone␈α
of␈αfour␈αcolors.␈α The␈α
object␈αof␈αthe␈α
puzzle␈αis␈αto␈α
build␈αa
␈↓ ↓H␈↓tower␈αof␈αall␈αfour␈αblocks␈αsuch␈αthat␈αeach␈αvertical␈αface␈αof␈αthe␈αtower␈αinvolves␈αall␈αfour␈αcolors.␈α In␈αorder
␈↓ ↓H␈↓to␈α∞use␈α∂the␈α∞above␈α∂defined␈α∞function␈α∞␈↓αsearch␈↓␈α∂for␈α∞this␈α∂purpose,␈α∞we␈α∞must␈α∂define␈α∞the␈α∂representation␈α∞of
␈↓ ↓H␈↓positions␈α
and␈α
give␈α
the␈α
functions␈α
␈↓αlose,␈α
ter,␈α
␈↓and␈α
␈↓αsuccessors␈↓.␈α
 A␈α
position␈α
is␈α
represented␈α
by␈α
a␈α
list␈αof␈α
lists
␈↓ ↓H␈↓¬␈α
one␈α
for␈α
each␈α
face␈α
of␈αthe␈α
tower.␈α
 Each␈α
sublist␈α
is␈α
the␈α
list␈αof␈α
colors␈α
of␈α
the␈α
faces␈α
of␈α
the␈αblocks␈α
showing
␈↓ ↓H␈↓in␈α⊃that␈α⊂face.␈α⊃ We␈α⊃shall␈α⊂assume␈α⊃that␈α⊂the␈α⊃blocks␈α⊃are␈α⊂described␈α⊃in␈α⊂the␈α⊃following␈α⊃longwinded␈α⊂but
␈↓ ↓H␈↓convenient␈αway.␈α (We'll␈αtake␈αup␈αprecomputing␈αthis␈αdescription␈αlater.)␈α For␈αeach␈αblock␈αthere␈αis␈αa␈αlist
␈↓ ↓H␈↓of␈αthe␈α
24␈αorientations␈α
of␈αthe␈α
block␈αwhere␈α
each␈αorientation␈α
is␈αdescribed␈α
as␈αa␈α
list␈αof␈α
the␈αcolors␈α
around
␈↓ ↓H␈↓the␈αvertical␈αfaces␈αof␈αthe␈αblock␈αwhen␈αit␈αis␈αin␈αthat␈αorientation.␈α Thus␈αthe␈αpuzzle␈αis␈αdescribed␈αby␈αa␈αlist
␈↓ ↓H␈↓of lists of lists which we shall call ␈↓αpuzz␈↓.
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :28


␈↓ ↓H␈↓        We now have

␈↓ ↓H␈↓        ␈↓αp␈↓¬0␈↓ ␈↓↓=␈↓ (NIL NIL NIL NIL),

␈↓ ↓H␈↓        ␈↓αlose p ␈↓↓←␈↓α orlis␈↓↓[␈↓αp, λu␈↓↓:␈↓α ␈↓βa ␈↓αu ␈↓↓ε ␈↓βd ␈↓αu␈↓↓]␈↓α,

␈↓ ↓H␈↓α␈↓        ␈↓αter p ␈↓↓← [␈↓αlength ␈↓βa ␈↓αp ␈↓↓=␈↓α 4␈↓↓]␈↓,

␈↓ ↓H␈↓and

␈↓ ↓H␈↓        ␈↓αsuccessors p ␈↓↓←␈↓α mapcar␈↓↓[␈↓βa ␈↓αnth␈↓↓[␈↓αpuzz, 1 + length ␈↓βa ␈↓αp␈↓↓]␈↓α , λx␈↓↓:␈↓α mapcar2␈↓↓[␈↓αp, x, λyz␈↓↓:␈↓α z.y␈↓↓]]␈↓α, ␈↓

␈↓ ↓H␈↓where

␈↓ ↓H␈↓        ␈↓αmapcar2␈↓↓[␈↓αu, v, f␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓NIL ␈↓βelse f␈↓↓[␈↓βa ␈↓αu, ␈↓βa ␈↓αv␈↓↓]␈↓α . mapcar2␈↓↓[␈↓βd ␈↓αu, ␈↓βd ␈↓αv, f␈↓↓]␈↓α.␈↓

␈↓ ↓H␈↓        Getting␈αthe␈αinitial␈αposition␈αin␈αthe␈αdesired␈αform␈αis␈αas␈αcomplicated␈αa␈αcomputation␈αas␈αthe␈αactual
␈↓ ↓H␈↓tree␈α∞search.␈α∞ It␈α∞can␈α∞be␈α∞conveniently␈α∞done␈α∞by␈α∞a␈α∞sequence␈α∞of␈α∞assignment␈α∞statements␈α∞starting␈α∞with␈α
a
␈↓ ↓H␈↓description of the blocks:

␈↓ ↓H␈↓        ␈↓αpuzz1 ␈↓↓← ␈↓((G B B W R G) (G G B G W R) (G W W R B R) (G G R B W W)).

␈↓ ↓H␈↓Here␈αeach␈αblock␈αis␈αrepresented␈αby␈αa␈αlist␈αof␈αthe␈αcolors␈αof␈αthe␈αfaces␈αstarting␈αwith␈αthe␈αtop␈αface,␈αgoing
␈↓ ↓H␈↓around the sides in a clockwise direction and finishing with the bottom face.

␈↓ ↓H␈↓        We␈αneed␈αto␈αgo␈αfrom␈αthis␈αdescription␈αof␈αthe␈αblocks␈αto␈αa␈αlist␈αof␈αthe␈αpossible␈αcycles␈αof␈αcolors␈αon
␈↓ ↓H␈↓the␈α
vertical␈α
faces␈α
for␈αthe␈α
24␈α
orientations␈α
of␈αthe␈α
block.␈α
 This␈α
not␈α
easy,␈αbecause␈α
the␈α
order␈α
in␈αwhich␈α
we
␈↓ ↓H␈↓have␈α∞given␈α
the␈α∞colors␈α∞is␈α
not␈α∞invariant␈α
under␈α∞rotations␈α∞of␈α
the␈α∞block.␈α
 An␈α∞easy␈α∞way␈α
out␈α∞is␈α∞to␈α
start
␈↓ ↓H␈↓with␈αa␈αblock␈αwhose␈αfaces␈αare␈αassigned␈αthe␈αnumbers␈α1␈αthru␈α6␈αstarting␈αwith␈αthe␈αtop,␈αgoing␈αclockwise
␈↓ ↓H␈↓around␈αthe␈αsides␈αand␈α
finishing␈αwith␈αthe␈αbottom.␈α
 We␈αwrite␈αdown␈αone␈α
cycle␈αof␈αside␈αcolors␈α
for␈αeach
␈↓ ↓H␈↓choice␈αof␈αthe␈α
face␈αput␈αon␈α
top␈αand␈αget␈αthe␈α
list␈αof␈αall␈α
24␈αcycles␈αby␈α
appending␈αthe␈αresults␈αof␈α
generating
␈↓ ↓H␈↓the cyclic permutations of the cycles.  All this is accomplished by the assignment\.

␈↓ ↓H␈↓        ␈↓αpuzz2 ␈↓↓←␈↓α cycles␈↓↓[␈↓(2 3 4 5)␈↓↓]␈↓␈↓↓*␈↓␈↓αcycles␈↓↓[␈↓α(␈↓(2 5 4 3)␈↓↓]␈↓␈↓↓*␈↓ ␈↓αcycles␈↓↓[␈↓α(1 2 6 4)␈↓↓]␈↓α
␈↓ ↓H␈↓α                  ␈↓↓*␈↓αcycles␈↓↓[␈↓α(1 4 6 2)␈↓↓]␈↓α␈↓↓*␈↓αcycles␈↓↓[␈↓α(1 3 6 5)␈↓↓]␈↓α␈↓↓*␈↓αcycles␈↓↓[␈↓α(1 5 6 3)␈↓↓]␈↓α, ␈↓

␈↓ ↓H␈↓where the function ␈↓αcycles␈↓ is defined by

␈↓ ↓H␈↓        ␈↓αcycles u ␈↓↓←␈↓α maplist␈↓↓[␈↓αu, λx␈↓↓:␈↓α x␈↓↓*␈↓αupto␈↓↓[␈↓αu, x␈↓↓]]␈↓

␈↓ ↓H␈↓with the auxiliary function


␈↓ ↓H␈↓        ␈↓αupto␈↓↓[␈↓αu, x␈↓↓] ← ␈↓βif ␈↓αx ␈↓βeq ␈↓αu ␈↓βthen ␈↓NIL ␈↓βelse a  ␈↓αu . upto␈↓↓[␈↓βd ␈↓αu, x␈↓↓]␈↓α.␈↓

␈↓ ↓H␈↓Next␈α
we␈α
create␈α
for␈α
each␈αblock␈α
a␈α
list␈α
of␈α
substitutions␈α
expressing␈αthe␈α
colors␈α
of␈α
the␈α
six␈αnumbered␈α
faces.
␈↓ ↓H␈↓We have
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :29


␈↓ ↓H␈↓        ␈↓αpuzz3 ␈↓↓←␈↓α mapcar␈↓↓[␈↓αpuzz1, λx␈↓↓:␈↓α prup␈↓↓[␈↓(1 2 3 4 5 6), ␈↓αx␈↓↓]]␈↓α, ␈↓

␈↓ ↓H␈↓and we use these substitutions to get for each block the list of 24 orientations of the block. Thus

␈↓ ↓H␈↓        ␈↓αpuzz4 ␈↓↓←␈↓α mapcar␈↓↓[␈↓αpuzz3, λs␈↓↓:␈↓α sublis␈↓↓[␈↓αs, puzz3␈↓↓]]␈↓α.

␈↓ ↓H␈↓αpuzz4␈↓␈α
has␈αall␈α
24␈α
orientations␈αof␈α
the␈α
first␈αblock␈α
while␈αfor␈α
symmetry␈α
reasons␈αwe␈α
need␈α
only␈αconsider
␈↓ ↓H␈↓three as distinct, say the first, ninth, and seventeen.  So we finally get

␈↓ ↓H␈↓        ␈↓αpuzz ␈↓↓← (␈↓βa ␈↓αnth␈↓↓[␈↓βa ␈↓αpuzz4, 1␈↓↓] ␈↓βa ␈↓αnth␈↓↓[␈↓βa ␈↓αpuzz4, 9␈↓↓] ␈↓βa ␈↓αnth␈↓↓[␈↓βa ␈↓αpuzz4, 17␈↓↓]) . ␈↓βd ␈↓αpuzz4.␈↓

␈↓ ↓H␈↓The program when compiled runs about 11 seconds on the PDP-10.

␈↓ ↓H␈↓        A␈α
more␈α
sophisticated␈α∞representation␈α
of␈α
face␈α∞cycles␈α
and␈α
partial␈α
towers␈α∞makes␈α
a␈α
factor␈α∞of␈α
ten
␈↓ ↓H␈↓speedup␈α
without␈αchanging␈α
the␈αbasic␈α
search␈αalgorithm.␈α
 A␈αface␈α
cycle␈αis␈α
represented␈αby␈α
16␈αbits␈α
in␈αa
␈↓ ↓H␈↓word␈αfour␈αfor␈αeach␈αface␈αa␈α
particular␈αone␈αof␈αwhich␈αbeing␈αturned␈αon␈α
tells␈αus␈αthe␈αcolor␈αof␈αthe␈αface.␈α
 If
␈↓ ↓H␈↓we␈α␈↓βor␈↓␈αthese␈αwords␈αtogether␈αfor␈αthe␈αblocks␈αin␈αa␈αpartial␈αtower␈αwe␈αget␈αa␈αword␈αwhich␈αtells␈αus␈αfor␈αeach
␈↓ ↓H␈↓face␈αof␈αthe␈αtower␈αwhat␈αcolors␈αhave␈αbeen␈αused.␈α A␈αparticular␈αface␈αcycle␈αfrom␈αthe␈αnext␈αblock␈αcan␈αbe
␈↓ ↓H␈↓added␈α⊂to␈α⊂the␈α⊂tower␈α⊂if␈α⊃the␈α⊂␈↓βand␈↓␈α⊂of␈α⊂its␈α⊂word␈α⊂with␈α⊃the␈α⊂word␈α⊂representing␈α⊂the␈α⊂tower␈α⊂is␈α⊃zero.␈α⊂ We
␈↓ ↓H␈↓represent␈αa␈αposition␈αby␈αa␈αlist␈αof␈αwords␈αrepresenting␈αits␈αpartial␈αtowers␈αwith␈α0␈αas␈αthe␈αlast␈αelement␈α
and
␈↓ ↓H␈↓the␈αhighest␈αpartial␈αtower␈α
as␈αthe␈αfirst␈αelement.␈α
 The␈αvirtue␈αof␈αthis␈α
representation␈αis␈αthat␈αit␈αmakes␈α
the
␈↓ ↓H␈↓description␈αof␈αthe␈αalgorithm␈αshort.␈α The␈αinitial␈αposition␈αis␈α(0).␈α The␈αnew␈α␈↓αpuzz␈↓␈αcan␈αbe␈αformed␈αfrom
␈↓ ↓H␈↓the old one by the assignment

␈↓ ↓H␈↓        ␈↓αpuzza ␈↓↓←␈↓α mapcar␈↓↓[␈↓αpuzz, λx␈↓↓:␈↓α mapcar␈↓↓[␈↓αx, zap␈↓↓]]␈↓α, ␈↓

␈↓ ↓H␈↓where

␈↓ ↓H␈↓        ␈↓αzap v ␈↓↓← ␈↓βif n ␈↓αv ␈↓βthen ␈↓∧0 ␈↓βelse ␈↓αpoo ␈↓βa ␈↓αv ␈↓↓+ 16 * ␈↓αzap ␈↓βd ␈↓αv, ␈↓\.

␈↓ ↓H␈↓and

␈↓ ↓H␈↓        ␈↓αpoo x ␈↓↓← ␈↓βif ␈↓αx␈↓↓=␈↓R ␈↓βthen ␈↓α1 ␈↓βelse if ␈↓αx␈↓↓=␈↓W ␈↓βthen  ␈↓2 ␈↓βelse if ␈↓αx␈↓↓=␈↓G ␈↓βthen ␈↓4 ␈↓βelse ␈↓8.

␈↓ ↓H␈↓Now we need the new functions ␈↓αlose, ter, ␈↓and ␈↓αsuccessors␈↓.  These are

␈↓ ↓H␈↓        ␈↓αlose p ␈↓↓← ␈↓βfalse␈↓α,

␈↓ ↓H␈↓α␈↓        ␈↓αter p ␈↓↓← [␈↓αlength p ␈↓↓=␈↓α 5␈↓↓]␈↓α, ␈↓

␈↓ ↓H␈↓and

␈↓ ↓H␈↓        ␈↓αsuccessors p ␈↓↓←␈↓α mapchoose␈↓↓[␈↓βa ␈↓αnth␈↓↓[␈↓αpuzza, length p␈↓↓]␈↓α, λx␈↓↓:␈↓α ␈↓βa ␈↓αp ␈↓βand ␈↓αx ␈↓↓=␈↓α 0, λx␈↓↓:␈↓α ␈↓↓[␈↓βa ␈↓αp ␈↓βor ␈↓αx␈↓↓]␈↓α . p␈↓↓]␈↓α.␈↓

␈↓ ↓H␈↓where
␈↓ ↓H␈↓        ␈↓αmapchoose␈↓↓[␈↓αu, pred, fn␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓NIL

␈↓ ↓H␈↓                ␈↓βelse if ␈↓αpred ␈↓βa ␈↓αu ␈↓βthen ␈↓αfn␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α . mapchoose␈↓↓[␈↓βd ␈↓αu , pred, fn␈↓↓] ␈↓β
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :30


␈↓ ↓H␈↓β␈↓                ␈↓βelse ␈↓αmapchoose␈↓↓[␈↓βd ␈↓αu, pred, fn␈↓↓]␈↓α.␈↓


␈↓ ↓H␈↓␈↓αlose␈↓␈α
is␈α
trivial,␈α
because␈α
the␈α
␈↓αmapchoose␈↓␈α
is␈α
used␈α
to␈α
make␈α
sure␈α
that␈α
only␈α
non-losing␈α
new␈α
positions␈α
are
␈↓ ↓H␈↓generated␈α∂by␈α∂␈↓αsuccessors␈↓.␈α∂ This␈α∂version␈α∂runs␈α∂in␈α⊂a␈α∂little␈α∂less␈α∂than␈α∂one␈α∂second␈α∂on␈α∂the␈α⊂PDP-10.␈α∂ A
␈↓ ↓H␈↓greater␈α∩speedup␈α∩can␈α⊃be␈α∩made␈α∩by␈α∩the␈α⊃application␈α∩of␈α∩some␈α⊃mathematics.␈α∩ In␈α∩fact,␈α∩with␈α⊃enough
␈↓ ↓H␈↓mathematics, extensive tree search is unnecessary in this problem.

␈↓ ↓H␈↓        ␈↓αsearch␈↓␈α∂is␈α∞used␈α∂when␈α∂we␈α∞want␈α∂to␈α∂search␈α∞a␈α∂tree␈α∂of␈α∞possibilities␈α∂for␈α∂a␈α∞solution␈α∂to␈α∂a␈α∞problem.
␈↓ ↓H␈↓What␈αif␈αwe␈αwant␈αto␈αfind␈αall␈αsolutions␈αto␈αa␈αproblem?␈α This␈αcan␈αbe␈αdone␈αwith␈αa␈αfunction␈α␈↓αallsol␈↓␈αthat
␈↓ ↓H␈↓uses the same ␈↓αlose, ter, ␈↓and ␈↓αsuccessors␈↓ functions as does ␈↓αsearch␈↓.  The simplest way to write ␈↓αallsol␈↓ is

␈↓ ↓H␈↓        ␈↓αallsol p ␈↓↓← ␈↓βif ␈↓αlose p ␈↓βthen ␈↓NIL ␈↓βelse if ␈↓αter p  ␈↓βthen ␈↓α(p) ␈↓βelse ␈↓αmapapp␈↓↓[␈↓αsuccessors p, allsol␈↓↓]␈↓α, ␈↓

␈↓ ↓H␈↓where

␈↓ ↓H␈↓        ␈↓αmapapp␈↓↓[␈↓αu, fn␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓NIL ␈↓βelse ␈↓αfn␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α . mappap␈↓↓[␈↓βd ␈↓αu, fn␈↓↓]␈↓α.␈↓

␈↓ ↓H␈↓This␈αform␈αof␈α
the␈αfunction␈αis␈αsomewhat␈α
inefficient␈αbecause␈αof␈αall␈α
the␈α␈↓αappend␈↓ing.␈α A␈α
more␈αefficient
␈↓ ↓H␈↓form uses an auxiliary function as follows:

␈↓ ↓H␈↓        ␈↓αallsol p ␈↓↓←␈↓α allsola␈↓↓[␈↓αp, ␈↓NIL␈↓↓]␈↓

␈↓ ↓H␈↓        ␈↓αallsola␈↓↓[␈↓αp, found␈↓↓] ← ␈↓βif ␈↓αlose p ␈↓βthen ␈↓αfound
␈↓ ↓H␈↓α                                        ␈↓βelse if ␈↓αter p ␈↓βthen ␈↓αp . found
␈↓ ↓H␈↓α                                        ␈↓βelse ␈↓αallsolb␈↓↓[␈↓αsuccessors p, found␈↓↓]␈↓α,


␈↓ ↓H␈↓α␈↓        ␈↓αallsolb␈↓↓[␈↓αu, found␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓αfound ␈↓βelse ␈↓αallsolb␈↓↓[␈↓βd ␈↓αu, allsola␈↓↓[␈↓βa ␈↓αu, found␈↓↓]]␈↓α.␈↓

␈↓ ↓H␈↓The␈α∩recursive␈α⊃program␈α∩structure␈α⊃that␈α∩arises␈α⊃here␈α∩is␈α∩common␈α⊃when␈α∩a␈α⊃list␈α∩is␈α⊃to␈α∩be␈α∩formed␈α⊃by
␈↓ ↓H␈↓recurring through a list structure.



␈↓ ↓H␈↓6.  ␈↓βGame trees.␈↓


␈↓ ↓H␈↓        The␈α∞positions␈α∞that␈α∞can␈α∞be␈α∞reached␈α∞from␈α∞an␈α∞initial␈α∞position␈α∞in␈α∞a␈α∞ game␈α∞ form␈α∞ a␈α∂ tree,␈α∞and
␈↓ ↓H␈↓deciding␈αwhat␈αmove␈αto␈αmake␈αoften␈αinvolves␈αsearching␈αthis␈αtree.␈α However,␈αgame␈αtrees␈αare␈αsearched
␈↓ ↓H␈↓in␈αa␈αdifferent␈αway␈α than␈αthe␈αtrees␈αwe␈αhave␈αlooked␈αat,␈αbecause␈αthe␈αopposing␈αinterests␈αof␈αthe␈αplayers
␈↓ ↓H␈↓makes␈α
it␈α
not␈αa␈α
search␈α
for␈α
a␈αjoint␈α
line␈α
 of␈α
 play␈α that␈α
will␈α
 lead␈α
 to␈α the␈α
 first␈α
 player␈α
winning,␈αbut
␈↓ ↓H␈↓rather a search for a strategy that will lead to a win regardless of what the other  player does.

␈↓ ↓H␈↓        The␈α  simplest␈α situation␈α is␈α characterized␈α by␈α a␈α function␈α␈↓αsuccessors␈↓␈αthat␈αgives␈αthe␈αpositions
␈↓ ↓H␈↓that␈αcan␈αbe␈αreached␈αin␈α one␈αmove,␈α a␈α predicate␈α ␈↓αter␈↓␈α that␈α tells␈α when␈αa␈αposition␈αis␈αto␈αbe␈αregarded
␈↓ ↓H␈↓as␈α_ terminal␈α↔ for␈α_ the␈α_ given␈α↔ analysis,␈α_ and␈α↔ a␈α_  function␈α_␈↓αimval␈↓␈α↔ that␈α_ gives␈α_ a␈α↔ number
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :31


␈↓ ↓H␈↓approximating␈α the␈α value␈α of␈αthe␈α
position␈αto␈αone␈αof␈αthe␈α
 players.␈α  We␈α shall␈α call␈α this␈α player␈α
 the
␈↓ ↓H␈↓maximizing␈α player␈α and␈α his␈αopponent␈αthe␈αminimizing␈αplayer.␈αUsually,␈αthe␈αnumerical␈αvalues␈αarise,
␈↓ ↓H␈↓because␈α∂the␈α⊂search␈α∂cannot␈α⊂be␈α∂carried␈α∂ out␈α⊂to␈α∂the␈α⊂end␈α∂of␈α∂the␈α⊂game,␈α∂and␈α⊂the␈α∂analysis␈α⊂stops␈α∂with
␈↓ ↓H␈↓reasonably␈αstatic␈α
positions␈αthat␈α can␈α
 be␈α evaluated␈α
 by␈α some␈α rule.␈α
  Naturally,␈α the␈αfunction␈α
 ␈↓αimval␈↓
␈↓ ↓H␈↓is␈α
 chosen␈α to␈α
 be␈α
 easy␈α to␈α
 calculate␈αand␈α
to␈α
correlate␈αwell␈α
with␈α
the␈αprobability␈α
that␈αthe␈α
 maximizing
␈↓ ↓H␈↓player  can win the position.

␈↓ ↓H␈↓        The␈αsimplest␈αrule␈αfor␈αfinding␈αthe␈αcorrect␈αmove␈αin␈αa␈αposition␈αuses␈αauxiliary␈αfunctions␈α␈↓αvalmax␈↓
␈↓ ↓H␈↓and␈α␈↓αvalmin␈↓␈α
that␈αgive␈αa␈α
value␈αto␈αa␈α
position␈αby␈α
using␈α␈↓αimval␈↓␈αif␈α
the␈αposition␈αis␈α
terminal␈αand␈αtaking␈α
the
␈↓ ↓H␈↓max or min of the successor positions otherwise.

␈↓ ↓H␈↓        For␈αthis␈αwe␈αwant␈αfunctions␈αfor␈αgetting␈αthe␈αmaximum␈αor␈αthe␈αminimum␈αof␈αa␈αfunction␈αon␈αa␈α
list,
␈↓ ↓H␈↓and they are defined as follows:

␈↓ ↓H␈↓        ␈↓αmaxlis␈↓↓[␈↓αu, f␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓α-␈↓↓∞␈↓α ␈↓βelse ␈↓α max␈↓↓[␈↓αf␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α, maxlis␈↓↓[␈↓βd ␈↓αu, f␈↓↓]]␈↓α, ␈↓

␈↓ ↓H␈↓and

␈↓ ↓H␈↓        ␈↓αminlis␈↓↓[␈↓αu, f␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓α␈↓↓∞␈↓α ␈↓βelse ␈↓α min␈↓↓[␈↓αf␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α, minlis␈↓↓[␈↓βd ␈↓αu, f␈↓↓]]␈↓α.␈↓

␈↓ ↓H␈↓In␈α
these␈α
functions,␈α-␈↓↓∞␈↓␈α
and␈α
␈↓↓∞␈↓␈αrepresent␈α
numbers␈α
that␈αare␈α
smaller␈α
and␈αlarger␈α
than␈α
any␈αactual␈α
values
␈↓ ↓H␈↓that␈αwill␈α
occur␈αin␈α
evaluating␈α␈↓αf␈↓.␈α
 If␈αthese␈α
numbers␈αare␈α
not␈αavailable,␈α
then␈αit␈α
is␈αnecessary␈α
to␈αprime␈α
the
␈↓ ↓H␈↓function␈α∩with␈α∩the␈α∩values␈α∩of␈α∩␈↓αf␈↓␈α∩applied␈α∩to␈α∪the␈α∩first␈α∩element␈α∩of␈α∩the␈α∩list,␈α∩and␈α∩the␈α∪functions␈α∩are
␈↓ ↓H␈↓meaningless␈αfor␈αnull␈αlists.␈α Iterative␈αversions␈αof␈αthe␈αfunctions␈αare␈αgenerally␈αbetter;␈αwe␈αgive␈αonly␈αthe
␈↓ ↓H␈↓iterative version of ␈↓αmaxlis␈↓, namely

␈↓ ↓H␈↓        ␈↓αmaxlis␈↓↓[␈↓αu, f␈↓↓] ←␈↓α maxlisa␈↓↓[␈↓αu, -␈↓↓∞␈↓α, f␈↓↓]␈↓α, ␈↓

␈↓ ↓H␈↓where

␈↓ ↓H␈↓        ␈↓αmaxlisa␈↓↓[␈↓αu, x, f␈↓↓] ← ␈↓αif n u ␈↓βthen ␈↓αx ␈↓βelse ␈↓αmaxlisa␈↓↓[␈↓βd ␈↓αu, max␈↓↓[␈↓αx, f␈↓↓[␈↓βa ␈↓αu␈↓↓]]␈↓α, f␈↓↓]␈↓α.␈↓

␈↓ ↓H␈↓We now have

␈↓ ↓H␈↓        ␈↓αvalmax p ␈↓↓← ␈↓βif ␈↓αter p ␈↓βthen ␈↓αimval p ␈↓βelse ␈↓αmaxlis␈↓↓[␈↓αsuccessors p, valmin␈↓↓]␈↓,

␈↓ ↓H␈↓and

␈↓ ↓H␈↓        ␈↓αvalmin p ␈↓↓← ␈↓βif ␈↓αter p ␈↓βthen ␈↓αimval p ␈↓βelse ␈↓αminlis␈↓↓[␈↓αsuccessors p, valmax␈↓↓]␈↓.

␈↓ ↓H␈↓The best move is now chosen by

␈↓ ↓H␈↓        ␈↓αmovemax p ␈↓↓←␈↓α bestmax␈↓↓[␈↓αsuccesors p, valmin␈↓↓]␈↓α, ␈↓

␈↓ ↓H␈↓or

␈↓ ↓H␈↓        ␈↓αmovemin p ␈↓↓←␈↓α bestmin␈↓↓[␈↓αsuccesors p, valmax␈↓↓]␈↓α, ␈↓
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :32


␈↓ ↓H␈↓where

␈↓ ↓H␈↓        ␈↓αbestmax␈↓↓[␈↓αu, f␈↓↓] ←␈↓α bestmaxa␈↓↓[␈↓βd ␈↓αu, ␈↓βa ␈↓αu, f␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α, f␈↓↓]␈↓α,

␈↓ ↓H␈↓α␈↓        ␈↓αbestmaxa␈↓↓[␈↓αu, sofar, valsofar, f␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓αsofar

␈↓ ↓H␈↓α␈↓                ␈↓α␈↓βelse if ␈↓αf␈↓↓[␈↓βa ␈↓αu␈↓↓] ≤ ␈↓αbestsofar ␈↓βthen ␈↓αbestmaxa␈↓↓[␈↓βd ␈↓αu, sofar, bestsofar, f␈↓↓]␈↓α
␈↓ ↓H␈↓α␈↓                ␈↓α␈↓βelse ␈↓αbestmaxa␈↓↓[␈↓βd ␈↓αu, ␈↓βa ␈↓αu, f␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α, f␈↓↓]␈↓α,

␈↓ ↓H␈↓α␈↓        ␈↓αbestmin␈↓↓[␈↓αu, f␈↓↓] ←␈↓α bestmina␈↓↓[␈↓βd ␈↓αu, ␈↓βa ␈↓αu, f␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α, f␈↓↓]␈↓α, ␈↓

␈↓ ↓H␈↓and

␈↓ ↓H␈↓        ␈↓αbestmina␈↓↓[␈↓αu, sofar, valsofar, f␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓αsofar

␈↓ ↓H␈↓α␈↓                ␈↓α␈↓βelse if ␈↓αf␈↓↓[␈↓βa ␈↓αu␈↓↓] ≥ ␈↓αbestsofar ␈↓βthen ␈↓αbestmina␈↓↓[␈↓βd ␈↓αu, sofar, bestsofar, f␈↓↓]␈↓α
␈↓ ↓H␈↓α␈↓                ␈↓α␈↓βelse ␈↓αbestmina␈↓↓[␈↓βd ␈↓αu, ␈↓βa ␈↓αu, f␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α, f␈↓↓]␈↓α.␈↓


␈↓ ↓H␈↓        However,␈αthis␈αstraight␈αminimax␈αcomputation␈αof␈αthe␈αbest␈αmove␈αdoes␈αmuch␈αmore␈αcomputation
␈↓ ↓H␈↓in␈αgeneral␈αthan␈αis␈αusually␈αnecessary.␈α The␈αsimplest␈αway␈αto␈αsee␈αthis␈αis␈αfrom␈αthe␈αmove␈αtree␈αof␈αFigure
␈↓ ↓H␈↓2.6.

␈↓"␈↓ ↓H␈↓␈↓ ¬H            ≤ 8
␈↓"␈↓ ↓H␈↓␈↓ ¬H      max ≤'
␈↓"␈↓ ↓H␈↓␈↓ ¬H         '␈↓ ↓H                                         αααα 1␈↓ ↓H                                        ≤≥
␈↓"␈↓ ↓H␈↓␈↓ ¬H  min ≤'  `≥
␈↓"␈↓ ↓H␈↓␈↓ ¬H    ≤'      ` 6
␈↓"␈↓ ↓H␈↓␈↓ ¬H   '␈↓ ↓H                                   ≥
␈↓"␈↓ ↓H␈↓␈↓ ¬H    `≥      ≤ 9
␈↓"␈↓ ↓H␈↓␈↓ ¬H      `≥  ≤'
␈↓"␈↓ ↓H␈↓␈↓ ¬H        `'␈↓ ↓H                                         αααα X␈↓ ↓H                                         ≥
␈↓"␈↓ ↓H␈↓␈↓ ¬H          `≥
␈↓"␈↓ ↓H␈↓␈↓ ¬H            ` X

␈↓ ↓H␈↓↔␈↓Figure 2.6␈↓


␈↓ ↓H␈↓We␈α
see␈αfrom␈α
this␈α
figure␈αthat␈α
it␈α
is␈αunnecessary␈α
to␈α
examine␈αthe␈α
moves␈α
marked␈αx,␈α
because␈αtheir␈α
values
␈↓ ↓H␈↓have␈α∂no␈α∞effect␈α∂on␈α∂the␈α∞value␈α∂of␈α∂the␈α∞game␈α∂or␈α∂on␈α∞the␈α∂correct␈α∂move␈α∞since␈α∂the␈α∂presence␈α∞of␈α∂the␈α∂9␈α∞is
␈↓ ↓H␈↓sufficient␈αinformation␈α
at␈αthis␈α
point␈αto␈α
show␈αthat␈αthe␈α
move␈αleading␈α
to␈αthe␈α
vertex␈αpreceding␈αit␈α
should
␈↓ ↓H␈↓not be chosen by the minimizing player.

␈↓ ↓H␈↓        The␈αgeneral␈αsituation␈αis␈αthat␈αit␈αis␈αunnecessary␈αto␈αexamine␈αfurther␈αmoves␈αin␈αa␈αposition␈αonce␈αa
␈↓ ↓H␈↓move␈α
is␈α
found␈α
that␈α
refutes␈α∞moving␈α
to␈α
the␈α
position␈α
in␈α
the␈α∞first␈α
place.␈α
 This␈α
idea␈α
is␈α
called␈α∞the␈α
αβ-
␈↓ ↓H␈↓heuristic and expressed in the following recursive definitions:
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :33


␈↓ ↓H␈↓        ␈↓αmaxval p ␈↓↓←␈↓α maxval1␈↓↓[␈↓αp, -␈↓↓∞␈↓α, ␈↓↓∞␈↓α␈↓↓]␈↓α,

␈↓ ↓H␈↓α          maxval1␈↓↓[␈↓αp,␈αα,␈α
β␈↓↓]␈α←␈α␈↓βif␈α
␈↓αter␈αp␈α␈↓βthen␈α
␈↓αmax␈↓↓[␈↓αα,␈αmin␈↓↓[␈↓αβ,␈αimval␈α
p␈↓↓]]␈↓α␈α ␈↓βelse␈α␈↓αmaxval2␈↓↓[␈↓αsuccessors␈α
p,␈αα,
␈↓ ↓H␈↓αβ␈↓↓]␈↓α,

␈↓ ↓H␈↓α          maxval2␈↓↓[␈↓αu, α, β␈↓↓] ← {␈↓αminval1␈↓↓[␈↓βa ␈↓αu, α, β␈↓↓]}[␈↓αλw␈↓↓:␈↓α ␈↓βif ␈↓αw ␈↓↓=␈↓α β ␈↓βthen  ␈↓αβ ␈↓βelse ␈↓αmaxval2␈↓↓[␈↓βd ␈↓αu, w, β␈↓↓]]␈↓α,

␈↓ ↓H␈↓α␈↓        ␈↓αminval p ␈↓↓←␈↓α minval1␈↓↓[␈↓αp, -␈↓↓∞␈↓α, ␈↓↓∞␈↓α␈↓↓]␈↓α,

␈↓ ↓H␈↓α          minval1␈↓↓[␈↓αp,␈α
α,␈α
β␈↓↓]␈α
←␈α
␈↓βif␈α
␈↓αter␈α
p␈α␈↓βthen␈α
␈↓αmax␈↓↓[␈↓αα,␈α
min␈↓↓[␈↓αβ,␈α
imval␈α
p␈↓↓]]␈↓α␈α
 ␈↓βelse␈α
␈↓αminval2␈↓↓[␈↓αsuccessors␈α
p,␈αα,
␈↓ ↓H␈↓αβ␈↓↓]␈↓α,

␈↓ ↓H␈↓α          minval2␈↓↓[␈↓αu, α, β␈↓↓] ← {␈↓αmaxval1␈↓↓[␈↓βa ␈↓αu, α, β␈↓↓]}[␈↓αλw␈↓↓:␈↓α ␈↓βif ␈↓αw ␈↓↓=␈↓α α ␈↓βthen  ␈↓αα ␈↓βelse ␈↓αminval2␈↓↓[␈↓βd ␈↓αu, α, w␈↓↓]␈↓α.␈↓

␈↓ ↓H␈↓        The␈αreduction␈α
in␈αnumber␈αof␈α
positions␈αexamined␈αgiven␈α
by␈αthe␈ααβ␈α
algorithm␈αover␈α
the␈αsimple
␈↓ ↓H␈↓minimax␈αalgorithm␈αdepends␈αon␈α
the␈αorder␈αin␈αwhich␈α
the␈αmoves␈αare␈αexamined.␈α
 In␈αthe␈αworst␈αcase,␈α
the
␈↓ ↓H␈↓moves␈αhappen␈αto␈αbe␈αexamined␈αin␈αinverse␈αorder␈αof␈α
merit␈αin␈αevery␈αposition␈αon␈αthe␈αtree,␈αi.e.␈αthe␈α
worst
␈↓ ↓H␈↓move␈α
first.␈α
 In␈α
that␈αcase,␈α
there␈α
is␈α
no␈αimprovement␈α
over␈α
minimax.␈α
 The␈α
best␈αcase␈α
is␈α
the␈α
one␈αin␈α
which
␈↓ ↓H␈↓the␈α
best␈α
move␈α
in␈αevery␈α
position␈α
is␈α
examined␈αfirst.␈α
 If␈α
we␈α
look␈α␈↓αn␈↓␈α
moves␈α
deep␈α
on␈αa␈α
tree␈α
that␈α
has␈α␈↓αk␈↓
␈↓ ↓H␈↓successors␈α
to␈α
each␈α
position,␈α
then␈α
minimax␈α
looks␈α
at␈α
␈↓αk␈↓εn␈↓␈α
positions␈α
while␈α
αβ␈α
looks␈α
at␈α
about␈α
only␈α␈↓αk␈↓εn/2␈↓.
␈↓ ↓H␈↓Thus␈α
a␈α
program␈α
that␈α
looks␈α
at␈α
10␈↓ε4␈↓␈α
moves␈α
with␈α
αβ␈α
might␈α
have␈α
to␈α
look␈α
at␈α
10␈↓ε8␈↓␈α
with␈α
minimax.␈α
 For
␈↓ ↓H␈↓this␈α
reason,␈α
game␈α
playing␈αprograms␈α
using␈α
αβ␈α
make␈αa␈α
big␈α
effort␈α
to␈αinclude␈α
as␈α
good␈α
as␈α
possible␈αan
␈↓ ↓H␈↓ordering␈α
of␈αmoves␈α
into␈α
the␈α␈↓αsuccessors␈↓␈α
function.␈α
 When␈αthere␈α
is␈α
a␈αdeep␈α
tree␈α
search␈αto␈α
be␈α
done,␈αthe
␈↓ ↓H␈↓way␈α∂to␈α⊂make␈α∂the␈α⊂ordering␈α∂is␈α∂with␈α⊂a␈α∂short␈α⊂look-ahead␈α∂to␈α∂a␈α⊂much␈α∂smaller␈α⊂depth␈α∂than␈α⊂the␈α∂main
␈↓ ↓H␈↓search.␈α∞ Still␈α∞shorter␈α∞look-aheads␈α∞are␈α∞used␈α∞deeper␈α∂in␈α∞the␈α∞tree,␈α∞and␈α∞beyond␈α∞a␈α∞certain␈α∂depth,␈α∞non-
␈↓ ↓H␈↓look-ahead ordering methods are of decreasing complexity.

␈↓ ↓H␈↓        A␈α∂version␈α∞of␈α∂αβ␈α∞incorporating␈α∂optimistic␈α∞and␈α∂pessimistic␈α∞evaluations␈α∂of␈α∞positions␈α∂was␈α∞first
␈↓ ↓H␈↓proposed␈α⊂by␈α⊂McCarthy␈α⊂about␈α⊂1958.␈α⊂ Edwards␈α⊂and␈α⊂Hart␈α⊂at␈α⊂M.I.T.␈α⊂about␈α⊂1959␈α⊂proved␈α⊃that␈α⊂the
␈↓ ↓H␈↓present␈α∂version␈α⊂of␈α∂αβ␈α∂works␈α⊂and␈α∂calculated␈α∂the␈α⊂improvement␈α∂it␈α∂gives␈α⊂over␈α∂minimax.␈α⊂ The␈α∂first
␈↓ ↓H␈↓publication,␈α
however,␈α
was␈α
Brudno␈α
(1963).␈α
 It␈α
is␈α
worth␈α
noting␈α
that␈α
αβ␈α
was␈α
not␈α
used␈α
in␈α
the␈α
early␈α
chess
␈↓ ↓H␈↓playing␈α⊂programs␈α⊃in␈α⊂spite␈α⊃of␈α⊂the␈α⊂fact␈α⊃that␈α⊂it␈α⊃is␈α⊂clearly␈α⊂used␈α⊃in␈α⊂any␈α⊃human␈α⊂play.␈α⊃ Its␈α⊂non-use,
␈↓ ↓H␈↓therefore,␈α∪represents␈α∪a␈α∪failure␈α∪of␈α∪self-observation.␈α∪ Very␈α∪likely,␈α∪there␈α∪are␈α∪a␈α∪number␈α∪of␈α∩other
␈↓ ↓H␈↓algorithms␈αused␈αin␈αhuman␈αthought␈αthat␈αwe␈α
have␈αnot␈αnoticed␈αan␈αincorporated␈αin␈αour␈αprograms.␈α
 To
␈↓ ↓H␈↓the␈αextent␈α
that␈αthis␈α
is␈αso,␈α
artificial␈αintelligence␈α
will␈αbe␈α
␈↓αa␈αposteriori␈↓␈α
obvious␈αeven␈α
though␈αit␈α
is␈α␈↓αa␈α
priori␈↓
␈↓ ↓H␈↓very difficult.